From patchwork Thu Mar 17 12:43: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: 34811 Delivered-To: ffmpegpatchwork2@gmail.com Received: by 2002:a05:6838:3486:0:0:0:0 with SMTP id ek6csp867038nkb; Thu, 17 Mar 2022 05:43:58 -0700 (PDT) X-Google-Smtp-Source: ABdhPJzxVIeZCM14Awjn4DISWfWNs9BlxwxX7NuLj+/zcACnRfYGIXPiw5/REPAms1r5g5q+/byg X-Received: by 2002:a17:906:9754:b0:6da:7d72:1353 with SMTP id o20-20020a170906975400b006da7d721353mr4225397ejy.273.1647521038418; Thu, 17 Mar 2022 05:43:58 -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 s15-20020a50d48f000000b00418e654a3ddsi1290337edi.341.2022.03.17.05.43.58; Thu, 17 Mar 2022 05:43:58 -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=EN7Fg58U; 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 CC9FA68B073; Thu, 17 Mar 2022 14:43:46 +0200 (EET) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from EUR05-VI1-obe.outbound.protection.outlook.com (mail-vi1eur05olkn2073.outbound.protection.outlook.com [40.92.90.73]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 7792968AF8A for ; Thu, 17 Mar 2022 14:43:40 +0200 (EET) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=QI/kWGo0wHtrDos5pj/lwC4vIBGE8aaqhM9igzW1BmgU0mcD9tr2tl41+xNix6LPk0Dbo8tfjK/JDM0IvlJefogcwjPtpZ4XI14IotshGGpNXBsTpPDlvELiJiDx2z2lW2M82p8i3msdd41C/Pf5Q2JviZlFKVPBaP+v0y7Jq0s7c+XPevqXGDkKtfyKEqezE869izJG3lGpy0htg9UKeM2zMoAMZEg9DaZpo0Q6DSWHyReonfCtzhVf1t1U2w3FktBgiqyPyJlwItc7AJsViVdXVxORNhW87LkozXv3ub/HMdIrITY9/5QaaVHpAxBqWqYClvhiQyZwDowtbOJxUw== 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=on1KwM2v3LpYRi83V4XlPf0JrPm7735dR3mJi6VhQz4=; b=e3+wdVHpkRtORhSUuMUzsbfnVInhKZjTfGJPjiXbDXtsY/sut5TL1MHhtZx4kUlYj/XTIp/9huPxuEVh7NB5aUYF0aGf8vm0QebYyfq7VY6pMf0Utj4x2LpuaHf0t7qL4u8eQP3NJVeR5xz4u0UHgpC9KksS9O4deGI66EKfOulA5gyUMkHLqa6y8jDAlkcN5bJ4gd4AqeM2ig8Hnildd/nD6P0s0CzhVjsBMwf9GARPJAUcEXCcnW3dFckXl0K001OG1DSjUMORMzMOFyMcPhqR/VIf+04OsPo52NpznILGgbgmg7AaZ4AKYkczrfYs9l22LAXgfP6vHZkevH+UdA== 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=on1KwM2v3LpYRi83V4XlPf0JrPm7735dR3mJi6VhQz4=; b=EN7Fg58UCOosGpM0aue51YPxKPKZLxNJgOJex85W5xbxOwiFkJGeaBmMtkS8GrXLWIEMheqBjw564e+iP/0Bbdkdr487P2X1GJIM7g9vCrJkjcYfZBhFr23xX1lEFG9MyHd+rYo/YksZCMaE2gntmof6Nl9rdmgP6TrKVnVG+6VSiyVQkgLl15b1HrNXjD2C3beXLfyDeIM0XLG2uBAdHxaRbm+HBUTqkHbdJUZt0XUuQRjB+kN3azZAG83sogyRga7htfoZ9C+HfhDVHAgqZ9uqb5H8ZYYDf9LNu0DAM+a2T5aRRdjFIwfU7pTPQsoKbH3QaXmmAtn0Xs0PuLAKTw== Received: from AS1PR01MB9564.eurprd01.prod.exchangelabs.com (2603:10a6:20b:4d1::16) by AM0PR01MB3811.eurprd01.prod.exchangelabs.com (2603:10a6:208:ba::19) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5081.14; Thu, 17 Mar 2022 12:43:39 +0000 Received: from AS1PR01MB9564.eurprd01.prod.exchangelabs.com ([fe80::9070:a5fd:e532:bdf8]) by AS1PR01MB9564.eurprd01.prod.exchangelabs.com ([fe80::9070:a5fd:e532:bdf8%3]) with mapi id 15.20.5081.016; Thu, 17 Mar 2022 12:43:39 +0000 From: Andreas Rheinhardt To: ffmpeg-devel@ffmpeg.org Date: Thu, 17 Mar 2022 13:43:17 +0100 Message-ID: X-Mailer: git-send-email 2.32.0 In-Reply-To: References: X-TMN: [AJAQCCcaiJU1oKP7H34HXU3Z2f3rGzLM] X-ClientProxiedBy: AS9PR06CA0037.eurprd06.prod.outlook.com (2603:10a6:20b:463::21) To AS1PR01MB9564.eurprd01.prod.exchangelabs.com (2603:10a6:20b:4d1::16) X-Microsoft-Original-Message-ID: <20220317124320.1123436-2-andreas.rheinhardt@outlook.com> MIME-Version: 1.0 X-MS-Exchange-MessageSentRepresentingType: 1 X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 1dabeefb-1ea5-466b-9ae1-08da0813c294 X-MS-Exchange-SLBlob-MailProps: gjx25WM8ZNWOqF554eOqJZAmA161EiKRjSXVb2sjAqK4F00VcmnyDa+TJsBaPGdcMaaeXgUoQ7lEaaGab1+YlAtoT6jxQpybMtxJh+EPHg1AHy70q3CiGBq9krH/dArHFDzPTHaDwlmC5kazMqjJmGosYHy9cOSwsblyiVOEVYLSqVFH7vfSyGJmNz5Z4++uFGhMiiV/nuRf0ZGwLl4AUy5RzQfjSr/AP3uX8SApHlGfVWtc1px9vq2cnT/8OShCDU2nsZ/eeKJGnimJgQIFmWFPKZSqMdlU0sVgnc1DiG2vKYcNbttF5Irar9+d2DDfTwFA2hJKVIfdDMM8tNEWy7Jk8ZxcewjQmtM8MDwxiZVcfb2ONzm/5FZY1oRVMqzRd6UteqjZdU+u8MD78PBINTJcfJBXaBPPcPji34s7Pej3Bre3nenX/Y0bNf6BVNa8gmcK8vNOyOkbW7Q/5OQ1xLCY7LOPNSrI050Xa5LS+lVG8LbPGwmljHU7/YNSObNKyBsVQ2X/p/rzeJDKe5H7jv5lZVDXfiy56h8TxaPi/j79SJaOsVkRqDCO/EqAhkAiBcHKvpNcRe34KMDb5XmKf/yaUPMjY94oibLHiUvc6brhThFyuBTmwg1nrUMIyhmJFhihHNo5EOBOdcN+XevOsvKTeknAKfUoy9bZqEfGoumT89UvF/o6VvR9hVHwRoy2OINRtiy+mVWxcChwAfxUWkxx5gyGqbvV44ViqliYQq4= X-MS-TrafficTypeDiagnostic: AM0PR01MB3811:EE_ X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: +YFoE5oVL8j1qr0D4DlRRNSNhlEj9XH8VE+g0cwoMXC3hLNbZ1qJrc+x9unITpBY0WtXW+IgD21WHG1ZnLBOuJwbLW2aIqXoYLVzx5LDa+0oCPcILaMBfuq4RfDTxSSuTHf/QE4XW83fTTmPcoHE8ISP9V7ggD3ZKNjdvG3yNWpNSt7lnkcZ8jki3/boY8iZZsYrwyuJ5QkPtm52SFjI+htWtOSU4+Gpiv0D5ef0Ogi6JDRKBU/GVWRLiz9siFnnCazIKlL4Ne72ZlY1cxlEKS1Tlj87DxtMyV48uKx6zFmnv/oT5FkvEgImZAvtjk1W2ZPns5M8LsjfzO5Z+NoPTdHGIB4nMF6DkJZnqE3EaKDnMzmeX40TCQEzfX38+YqlVsWE6yo7RNjON8J2SjjrZCM82VOhi4c/Eq414+pEnLfTTnbvlaFrV+wcp0p+LsQfBJWKndpElLSp93SQIBt5UAz1V+JvnE3z+rgqW6k8B3EQog1a6y14/YujvE2iiOTyppGpU4BqOn4VHAZcDflJ03Hn/NKqiwkJMdQ40twjHBjSMeAtasttDwTt/Oozwa6DMW6lulfQSzALRcST/eFU+A== X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: p4bRiGExA307IWHfLxe7UH2818tk2sQe3C9YwFEH8/EQtvmixl0lXp50kRfS3PNBbQkwq1wF8S1UEL8jrK0jzjl1sUXvDqMIkapC8ulBRBiRfM7XvazhXruI1tX86fyVTq/36m4zn7dhEIu65yKuOW6lhEojR0WqDorjiV4RFCFwdU9krqHptazDveoPyIMSOSFE099Z1dUQ4jxoadYUPD+a2o+occIQOLhQFaR0hSW9ve714FaXM6E80PGyCfudUBQBiAHuKDHe1wRajHBjxjcKOwa4g0Tcr7d2MCYwgR1bF/BGy2ni0EEpi3v9eLqesPLznreyR3x6nxS3Qb015A4bBBcjSsQxz/V0zFXnN3P1zLkWHtwAgiN7yYgcxRVuPQCq0oAEv88mtCKuXADTFJc5GJEna6tB3+XPgjqotXJbzOYGo+NLcbo2o2mudVa7kjrjaRYl5KEn5m+G8EsM6/VEMqeEfn9IH7FWnPEKIA3lZcmwMJhqPr4vwTIdptWhDxGl83zDk6CK0Dcvk0HMVWUastQbimyOojTwB+dtJZ5mdMw2jiSbmO4AYAASjsY67jd16AL/4YbcMevTP/i9FyAjIoQxYh/SVGrHgOLBpxrFE9N0KXPYcTpQyvxir0qVktfa1vYTafJL6Yd3p1sxKRCLyFdteRG7p913A4OFBcOitP+wjODHP1qg0iZrY4FhqTslR83HNgiB11IiYu/1l/Nideh8QDmqKXb7KAziFx1gdYhiujn9cSzz/iK/fi1wxJqjZAIYl4kuT+fTnzYTXHdYDE0KgFvoEj5m23OaiGipEJfMMxSV6ROBw3Ok7zcR1MiugLa5HYUZf+Zd5aw54Z4bTgzwfgYTOh7weYh6kYR3QZejhcjjbsuzCY9lMRsVoo2HevYQQjZGX41i6zmfRaPfSOscLQYJoBU2c0c2NUwGcB9Gy2RFq792NvDaAoWXgjiPTP2kvUMwhCSZIXvGjxzVeeNdZAbTgvZhEi7H4D1iem910L5oxGDgja+NeznvdT6W4nfx1kam5LZ/6hTteyc4yJQEB6kJxhT63SVV1THthniKPKlHzIt5X7mSva14fHIYZjOGgKrZFY2MWwz+pld1l0bFZZkW03E59BO27I7CcQrm1LlGp+4Ut8YnTUx/JSgXLj3TqPzA1jik6uJLLI9z/dwcgclzdtTWMjrOHcA= X-OriginatorOrg: outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: 1dabeefb-1ea5-466b-9ae1-08da0813c294 X-MS-Exchange-CrossTenant-AuthSource: AS1PR01MB9564.eurprd01.prod.exchangelabs.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 17 Mar 2022 12:43:39.1234 (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: AM0PR01MB3811 Subject: [FFmpeg-devel] [PATCH 5/7] avcodec/bitstream: Move code for initializing VLCs to file of its own 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: 72VoBWuW01MP bitstream.c is currently the disjoint union of three parts: The first part is ff_log2_run, the second part are some auxiliary functions for the PutBits-API; and the third part is the code for creating VLCs. This commit moves the latter into a file of its own. This has the advantage of making one of the hacks in tableprint_vlc.h redundant as vlc.c does not include config.h (whereas the PutBits-API part does). Signed-off-by: Andreas Rheinhardt --- libavcodec/Makefile | 1 + libavcodec/bitstream.c | 349 --------------------------------- libavcodec/tableprint_vlc.h | 4 +- libavcodec/vlc.c | 378 ++++++++++++++++++++++++++++++++++++ 4 files changed, 380 insertions(+), 352 deletions(-) create mode 100644 libavcodec/vlc.c diff --git a/libavcodec/Makefile b/libavcodec/Makefile index 1905258f43..43fcf691a3 100644 --- a/libavcodec/Makefile +++ b/libavcodec/Makefile @@ -55,6 +55,7 @@ OBJS = ac3_parser.o \ qsv_api.o \ raw.o \ utils.o \ + vlc.o \ vorbis_parser.o \ xiph.o \ diff --git a/libavcodec/bitstream.c b/libavcodec/bitstream.c index 04817f9a84..36a980646d 100644 --- a/libavcodec/bitstream.c +++ b/libavcodec/bitstream.c @@ -28,23 +28,13 @@ * bitstream api. */ -#include #include -#include #include #include "config.h" #include "libavutil/avassert.h" -#include "libavutil/error.h" -#include "libavutil/internal.h" #include "libavutil/intreadwrite.h" -#include "libavutil/log.h" -#include "libavutil/macros.h" -#include "libavutil/mem.h" -#include "libavutil/qsort.h" -#include "libavutil/reverse.h" #include "put_bits.h" -#include "vlc.h" const uint8_t ff_log2_run[41]={ 0, 0, 0, 0, 1, 1, 1, 1, @@ -89,342 +79,3 @@ void ff_copy_bits(PutBitContext *pb, const uint8_t *src, int length) put_bits(pb, bits, AV_RB16(src + 2 * words) >> (16 - bits)); } - -/* VLC decoding */ - -#define GET_DATA(v, table, i, wrap, size) \ -{ \ - const uint8_t *ptr = (const uint8_t *)table + i * wrap; \ - switch(size) { \ - case 1: \ - v = *(const uint8_t *)ptr; \ - break; \ - case 2: \ - v = *(const uint16_t *)ptr; \ - break; \ - case 4: \ - default: \ - av_assert1(size == 4); \ - v = *(const uint32_t *)ptr; \ - break; \ - } \ -} - - -static int alloc_table(VLC *vlc, int size, int use_static) -{ - int index = vlc->table_size; - - vlc->table_size += size; - if (vlc->table_size > vlc->table_allocated) { - if (use_static) - abort(); // cannot do anything, init_vlc() is used with too little memory - vlc->table_allocated += (1 << vlc->bits); - vlc->table = av_realloc_f(vlc->table, vlc->table_allocated, sizeof(VLC_TYPE) * 2); - if (!vlc->table) { - vlc->table_allocated = 0; - vlc->table_size = 0; - return AVERROR(ENOMEM); - } - memset(vlc->table + vlc->table_allocated - (1 << vlc->bits), 0, sizeof(VLC_TYPE) * 2 << vlc->bits); - } - return index; -} - -#define LOCALBUF_ELEMS 1500 // the maximum currently needed is 1296 by rv34 - -static av_always_inline uint32_t bitswap_32(uint32_t x) -{ - return (uint32_t)ff_reverse[ x & 0xFF] << 24 | - (uint32_t)ff_reverse[(x >> 8) & 0xFF] << 16 | - (uint32_t)ff_reverse[(x >> 16) & 0xFF] << 8 | - (uint32_t)ff_reverse[ x >> 24]; -} - -typedef struct VLCcode { - uint8_t bits; - VLC_TYPE symbol; - /** codeword, with the first bit-to-be-read in the msb - * (even if intended for a little-endian bitstream reader) */ - uint32_t code; -} VLCcode; - -static int vlc_common_init(VLC *vlc, int nb_bits, int nb_codes, - VLCcode **buf, int flags) -{ - vlc->bits = nb_bits; - vlc->table_size = 0; - if (flags & INIT_VLC_USE_NEW_STATIC) { - av_assert0(nb_codes <= LOCALBUF_ELEMS); - } else { - vlc->table = NULL; - vlc->table_allocated = 0; - } - if (nb_codes > LOCALBUF_ELEMS) { - *buf = av_malloc_array(nb_codes, sizeof(VLCcode)); - if (!*buf) - return AVERROR(ENOMEM); - } - - return 0; -} - -static int compare_vlcspec(const void *a, const void *b) -{ - const VLCcode *sa = a, *sb = b; - return (sa->code >> 1) - (sb->code >> 1); -} -/** - * Build VLC decoding tables suitable for use with get_vlc(). - * - * @param vlc the context to be initialized - * - * @param table_nb_bits max length of vlc codes to store directly in this table - * (Longer codes are delegated to subtables.) - * - * @param nb_codes number of elements in codes[] - * - * @param codes descriptions of the vlc codes - * These must be ordered such that codes going into the same subtable are contiguous. - * Sorting by VLCcode.code is sufficient, though not necessary. - */ -static int build_table(VLC *vlc, int table_nb_bits, int nb_codes, - VLCcode *codes, int flags) -{ - int table_size, table_index, index, code_prefix, symbol, subtable_bits; - int i, j, k, n, nb, inc; - VLC_TYPE (*table)[2]; - uint32_t code; - - if (table_nb_bits > 30) - return AVERROR(EINVAL); - table_size = 1 << table_nb_bits; - table_index = alloc_table(vlc, table_size, flags & INIT_VLC_USE_NEW_STATIC); - ff_dlog(NULL, "new table index=%d size=%d\n", table_index, table_size); - if (table_index < 0) - return table_index; - table = &vlc->table[table_index]; - - /* first pass: map codes and compute auxiliary table sizes */ - for (i = 0; i < nb_codes; i++) { - n = codes[i].bits; - code = codes[i].code; - symbol = codes[i].symbol; - ff_dlog(NULL, "i=%d n=%d code=0x%"PRIx32"\n", i, n, code); - if (n <= table_nb_bits) { - /* no need to add another table */ - j = code >> (32 - table_nb_bits); - nb = 1 << (table_nb_bits - n); - inc = 1; - if (flags & INIT_VLC_OUTPUT_LE) { - j = bitswap_32(code); - inc = 1 << n; - } - for (k = 0; k < nb; k++) { - int bits = table[j][1]; - int oldsym = table[j][0]; - ff_dlog(NULL, "%4x: code=%d n=%d\n", j, i, n); - if ((bits || oldsym) && (bits != n || oldsym != symbol)) { - av_log(NULL, AV_LOG_ERROR, "incorrect codes\n"); - return AVERROR_INVALIDDATA; - } - table[j][1] = n; //bits - table[j][0] = symbol; - j += inc; - } - } else { - /* fill auxiliary table recursively */ - n -= table_nb_bits; - code_prefix = code >> (32 - table_nb_bits); - subtable_bits = n; - codes[i].bits = n; - codes[i].code = code << table_nb_bits; - for (k = i+1; k < nb_codes; k++) { - n = codes[k].bits - table_nb_bits; - if (n <= 0) - break; - code = codes[k].code; - if (code >> (32 - table_nb_bits) != code_prefix) - break; - codes[k].bits = n; - codes[k].code = code << table_nb_bits; - subtable_bits = FFMAX(subtable_bits, n); - } - subtable_bits = FFMIN(subtable_bits, table_nb_bits); - j = (flags & INIT_VLC_OUTPUT_LE) ? bitswap_32(code_prefix) >> (32 - table_nb_bits) : code_prefix; - table[j][1] = -subtable_bits; - ff_dlog(NULL, "%4x: n=%d (subtable)\n", - j, codes[i].bits + table_nb_bits); - index = build_table(vlc, subtable_bits, k-i, codes+i, flags); - if (index < 0) - return index; - /* note: realloc has been done, so reload tables */ - table = &vlc->table[table_index]; - table[j][0] = index; //code - if (table[j][0] != index) { - avpriv_request_sample(NULL, "strange codes"); - return AVERROR_PATCHWELCOME; - } - i = k-1; - } - } - - for (i = 0; i < table_size; i++) { - if (table[i][1] == 0) //bits - table[i][0] = -1; //codes - } - - return table_index; -} - -static int vlc_common_end(VLC *vlc, int nb_bits, int nb_codes, VLCcode *codes, - int flags, VLCcode localbuf[LOCALBUF_ELEMS]) -{ - int ret = build_table(vlc, nb_bits, nb_codes, codes, flags); - - if (flags & INIT_VLC_USE_NEW_STATIC) { - if (vlc->table_size != vlc->table_allocated && - !(flags & (INIT_VLC_STATIC_OVERLONG & ~INIT_VLC_USE_NEW_STATIC))) - av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n", vlc->table_size, vlc->table_allocated); - av_assert0(ret >= 0); - } else { - if (codes != localbuf) - av_free(codes); - if (ret < 0) { - av_freep(&vlc->table); - return ret; - } - } - return 0; -} - -/* Build VLC decoding tables suitable for use with get_vlc(). - - 'nb_bits' sets the decoding table size (2^nb_bits) entries. The - bigger it is, the faster is the decoding. But it should not be too - big to save memory and L1 cache. '9' is a good compromise. - - 'nb_codes' : number of vlcs codes - - 'bits' : table which gives the size (in bits) of each vlc code. - - 'codes' : table which gives the bit pattern of of each vlc code. - - 'symbols' : table which gives the values to be returned from get_vlc(). - - 'xxx_wrap' : give the number of bytes between each entry of the - 'bits' or 'codes' tables. - - 'xxx_size' : gives the number of bytes of each entry of the 'bits' - or 'codes' tables. Currently 1,2 and 4 are supported. - - 'wrap' and 'size' make it possible to use any memory configuration and types - (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables. -*/ -int ff_init_vlc_sparse(VLC *vlc, int nb_bits, int nb_codes, - const void *bits, int bits_wrap, int bits_size, - const void *codes, int codes_wrap, int codes_size, - const void *symbols, int symbols_wrap, int symbols_size, - int flags) -{ - VLCcode localbuf[LOCALBUF_ELEMS], *buf = localbuf; - int i, j, ret; - - ret = vlc_common_init(vlc, nb_bits, nb_codes, &buf, flags); - if (ret < 0) - return ret; - - av_assert0(symbols_size <= 2 || !symbols); - j = 0; -#define COPY(condition)\ - for (i = 0; i < nb_codes; i++) { \ - unsigned len; \ - GET_DATA(len, bits, i, bits_wrap, bits_size); \ - if (!(condition)) \ - continue; \ - if (len > 3*nb_bits || len > 32) { \ - av_log(NULL, AV_LOG_ERROR, "Too long VLC (%u) in init_vlc\n", len);\ - if (buf != localbuf) \ - av_free(buf); \ - return AVERROR(EINVAL); \ - } \ - buf[j].bits = len; \ - GET_DATA(buf[j].code, codes, i, codes_wrap, codes_size); \ - if (buf[j].code >= (1LL< nb_bits); - // qsort is the slowest part of init_vlc, and could probably be improved or avoided - AV_QSORT(buf, j, struct VLCcode, compare_vlcspec); - COPY(len && len <= nb_bits); - nb_codes = j; - - return vlc_common_end(vlc, nb_bits, nb_codes, buf, - flags, localbuf); -} - -int ff_init_vlc_from_lengths(VLC *vlc, int nb_bits, int nb_codes, - const int8_t *lens, int lens_wrap, - const void *symbols, int symbols_wrap, int symbols_size, - int offset, int flags, void *logctx) -{ - VLCcode localbuf[LOCALBUF_ELEMS], *buf = localbuf; - uint64_t code; - int ret, j, len_max = FFMIN(32, 3 * nb_bits); - - ret = vlc_common_init(vlc, nb_bits, nb_codes, &buf, flags); - if (ret < 0) - return ret; - - j = code = 0; - for (int i = 0; i < nb_codes; i++, lens += lens_wrap) { - int len = *lens; - if (len > 0) { - unsigned sym; - - buf[j].bits = len; - if (symbols) - GET_DATA(sym, symbols, i, symbols_wrap, symbols_size) - else - sym = i; - buf[j].symbol = sym + offset; - buf[j++].code = code; - } else if (len < 0) { - len = -len; - } else - continue; - if (len > len_max || code & ((1U << (32 - len)) - 1)) { - av_log(logctx, AV_LOG_ERROR, "Invalid VLC (length %u)\n", len); - goto fail; - } - code += 1U << (32 - len); - if (code > UINT32_MAX + 1ULL) { - av_log(logctx, AV_LOG_ERROR, "Overdetermined VLC tree\n"); - goto fail; - } - } - return vlc_common_end(vlc, nb_bits, j, buf, flags, localbuf); -fail: - if (buf != localbuf) - av_free(buf); - return AVERROR_INVALIDDATA; -} - -void ff_free_vlc(VLC *vlc) -{ - av_freep(&vlc->table); -} diff --git a/libavcodec/tableprint_vlc.h b/libavcodec/tableprint_vlc.h index 924f97b466..d53ae5799f 100644 --- a/libavcodec/tableprint_vlc.h +++ b/libavcodec/tableprint_vlc.h @@ -23,7 +23,6 @@ #ifndef AVCODEC_TABLEPRINT_VLC_H #define AVCODEC_TABLEPRINT_VLC_H -#define FFMPEG_CONFIG_H #define AVUTIL_LOG_H #define av_log(a, ...) while(0) #define ff_dlog(a, ...) while(0) @@ -37,9 +36,8 @@ #define avpriv_request_sample(...) #include "tableprint.h" #include "vlc.h" -#include "mathtables.c" #include "libavutil/reverse.c" -#include "bitstream.c" +#include "vlc.c" #define REPLACE_DEFINE2(type) write_##type##_array #define REPLACE_DEFINE(type) REPLACE_DEFINE2(type) diff --git a/libavcodec/vlc.c b/libavcodec/vlc.c new file mode 100644 index 0000000000..1a9bd8e6d2 --- /dev/null +++ b/libavcodec/vlc.c @@ -0,0 +1,378 @@ +/* + * API for creating VLC trees + * Copyright (c) 2000, 2001 Fabrice Bellard + * Copyright (c) 2002-2004 Michael Niedermayer + * Copyright (c) 2010 Loren Merritt + * + * This file is part of FFmpeg. + * + * FFmpeg is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * FFmpeg is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with FFmpeg; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include +#include +#include +#include + +#include "libavutil/attributes.h" +#include "libavutil/avassert.h" +#include "libavutil/error.h" +#include "libavutil/internal.h" +#include "libavutil/log.h" +#include "libavutil/macros.h" +#include "libavutil/mem.h" +#include "libavutil/qsort.h" +#include "libavutil/reverse.h" +#include "vlc.h" + +#define GET_DATA(v, table, i, wrap, size) \ +{ \ + const uint8_t *ptr = (const uint8_t *)table + i * wrap; \ + switch(size) { \ + case 1: \ + v = *(const uint8_t *)ptr; \ + break; \ + case 2: \ + v = *(const uint16_t *)ptr; \ + break; \ + case 4: \ + default: \ + av_assert1(size == 4); \ + v = *(const uint32_t *)ptr; \ + break; \ + } \ +} + + +static int alloc_table(VLC *vlc, int size, int use_static) +{ + int index = vlc->table_size; + + vlc->table_size += size; + if (vlc->table_size > vlc->table_allocated) { + if (use_static) + abort(); // cannot do anything, init_vlc() is used with too little memory + vlc->table_allocated += (1 << vlc->bits); + vlc->table = av_realloc_f(vlc->table, vlc->table_allocated, sizeof(VLC_TYPE) * 2); + if (!vlc->table) { + vlc->table_allocated = 0; + vlc->table_size = 0; + return AVERROR(ENOMEM); + } + memset(vlc->table + vlc->table_allocated - (1 << vlc->bits), 0, sizeof(VLC_TYPE) * 2 << vlc->bits); + } + return index; +} + +#define LOCALBUF_ELEMS 1500 // the maximum currently needed is 1296 by rv34 + +static av_always_inline uint32_t bitswap_32(uint32_t x) +{ + return (uint32_t)ff_reverse[ x & 0xFF] << 24 | + (uint32_t)ff_reverse[(x >> 8) & 0xFF] << 16 | + (uint32_t)ff_reverse[(x >> 16) & 0xFF] << 8 | + (uint32_t)ff_reverse[ x >> 24]; +} + +typedef struct VLCcode { + uint8_t bits; + VLC_TYPE symbol; + /** codeword, with the first bit-to-be-read in the msb + * (even if intended for a little-endian bitstream reader) */ + uint32_t code; +} VLCcode; + +static int vlc_common_init(VLC *vlc, int nb_bits, int nb_codes, + VLCcode **buf, int flags) +{ + vlc->bits = nb_bits; + vlc->table_size = 0; + if (flags & INIT_VLC_USE_NEW_STATIC) { + av_assert0(nb_codes <= LOCALBUF_ELEMS); + } else { + vlc->table = NULL; + vlc->table_allocated = 0; + } + if (nb_codes > LOCALBUF_ELEMS) { + *buf = av_malloc_array(nb_codes, sizeof(VLCcode)); + if (!*buf) + return AVERROR(ENOMEM); + } + + return 0; +} + +static int compare_vlcspec(const void *a, const void *b) +{ + const VLCcode *sa = a, *sb = b; + return (sa->code >> 1) - (sb->code >> 1); +} + +/** + * Build VLC decoding tables suitable for use with get_vlc(). + * + * @param vlc the context to be initialized + * + * @param table_nb_bits max length of vlc codes to store directly in this table + * (Longer codes are delegated to subtables.) + * + * @param nb_codes number of elements in codes[] + * + * @param codes descriptions of the vlc codes + * These must be ordered such that codes going into the same subtable are contiguous. + * Sorting by VLCcode.code is sufficient, though not necessary. + */ +static int build_table(VLC *vlc, int table_nb_bits, int nb_codes, + VLCcode *codes, int flags) +{ + int table_size, table_index; + VLC_TYPE (*table)[2]; + + if (table_nb_bits > 30) + return AVERROR(EINVAL); + table_size = 1 << table_nb_bits; + table_index = alloc_table(vlc, table_size, flags & INIT_VLC_USE_NEW_STATIC); + ff_dlog(NULL, "new table index=%d size=%d\n", table_index, table_size); + if (table_index < 0) + return table_index; + table = &vlc->table[table_index]; + + /* first pass: map codes and compute auxiliary table sizes */ + for (int i = 0; i < nb_codes; i++) { + int n = codes[i].bits; + uint32_t code = codes[i].code; + int symbol = codes[i].symbol; + ff_dlog(NULL, "i=%d n=%d code=0x%"PRIx32"\n", i, n, code); + if (n <= table_nb_bits) { + /* no need to add another table */ + int j = code >> (32 - table_nb_bits); + int nb = 1 << (table_nb_bits - n); + int inc = 1; + + if (flags & INIT_VLC_OUTPUT_LE) { + j = bitswap_32(code); + inc = 1 << n; + } + for (int k = 0; k < nb; k++) { + int bits = table[j][1]; + int oldsym = table[j][0]; + ff_dlog(NULL, "%4x: code=%d n=%d\n", j, i, n); + if ((bits || oldsym) && (bits != n || oldsym != symbol)) { + av_log(NULL, AV_LOG_ERROR, "incorrect codes\n"); + return AVERROR_INVALIDDATA; + } + table[j][1] = n; //bits + table[j][0] = symbol; + j += inc; + } + } else { + /* fill auxiliary table recursively */ + uint32_t code_prefix; + int index, subtable_bits, j, k; + + n -= table_nb_bits; + code_prefix = code >> (32 - table_nb_bits); + subtable_bits = n; + codes[i].bits = n; + codes[i].code = code << table_nb_bits; + for (k = i + 1; k < nb_codes; k++) { + n = codes[k].bits - table_nb_bits; + if (n <= 0) + break; + code = codes[k].code; + if (code >> (32 - table_nb_bits) != code_prefix) + break; + codes[k].bits = n; + codes[k].code = code << table_nb_bits; + subtable_bits = FFMAX(subtable_bits, n); + } + subtable_bits = FFMIN(subtable_bits, table_nb_bits); + j = (flags & INIT_VLC_OUTPUT_LE) ? bitswap_32(code_prefix) >> (32 - table_nb_bits) : code_prefix; + table[j][1] = -subtable_bits; + ff_dlog(NULL, "%4x: n=%d (subtable)\n", + j, codes[i].bits + table_nb_bits); + index = build_table(vlc, subtable_bits, k-i, codes+i, flags); + if (index < 0) + return index; + /* note: realloc has been done, so reload tables */ + table = &vlc->table[table_index]; + table[j][0] = index; //code + if (table[j][0] != index) { + avpriv_request_sample(NULL, "strange codes"); + return AVERROR_PATCHWELCOME; + } + i = k-1; + } + } + + for (int i = 0; i < table_size; i++) { + if (table[i][1] == 0) //bits + table[i][0] = -1; //codes + } + + return table_index; +} + +static int vlc_common_end(VLC *vlc, int nb_bits, int nb_codes, VLCcode *codes, + int flags, VLCcode localbuf[LOCALBUF_ELEMS]) +{ + int ret = build_table(vlc, nb_bits, nb_codes, codes, flags); + + if (flags & INIT_VLC_USE_NEW_STATIC) { + if (vlc->table_size != vlc->table_allocated && + !(flags & (INIT_VLC_STATIC_OVERLONG & ~INIT_VLC_USE_NEW_STATIC))) + av_log(NULL, AV_LOG_ERROR, "needed %d had %d\n", vlc->table_size, vlc->table_allocated); + av_assert0(ret >= 0); + } else { + if (codes != localbuf) + av_free(codes); + if (ret < 0) { + av_freep(&vlc->table); + return ret; + } + } + return 0; +} + +/* Build VLC decoding tables suitable for use with get_vlc(). + + 'nb_bits' sets the decoding table size (2^nb_bits) entries. The + bigger it is, the faster is the decoding. But it should not be too + big to save memory and L1 cache. '9' is a good compromise. + + 'nb_codes' : number of vlcs codes + + 'bits' : table which gives the size (in bits) of each vlc code. + + 'codes' : table which gives the bit pattern of of each vlc code. + + 'symbols' : table which gives the values to be returned from get_vlc(). + + 'xxx_wrap' : give the number of bytes between each entry of the + 'bits' or 'codes' tables. + + 'xxx_size' : gives the number of bytes of each entry of the 'bits' + or 'codes' tables. Currently 1,2 and 4 are supported. + + 'wrap' and 'size' make it possible to use any memory configuration and types + (byte/word/long) to store the 'bits', 'codes', and 'symbols' tables. +*/ +int ff_init_vlc_sparse(VLC *vlc, int nb_bits, int nb_codes, + const void *bits, int bits_wrap, int bits_size, + const void *codes, int codes_wrap, int codes_size, + const void *symbols, int symbols_wrap, int symbols_size, + int flags) +{ + VLCcode localbuf[LOCALBUF_ELEMS], *buf = localbuf; + int j, ret; + + ret = vlc_common_init(vlc, nb_bits, nb_codes, &buf, flags); + if (ret < 0) + return ret; + + av_assert0(symbols_size <= 2 || !symbols); + j = 0; +#define COPY(condition)\ + for (int i = 0; i < nb_codes; i++) { \ + unsigned len; \ + GET_DATA(len, bits, i, bits_wrap, bits_size); \ + if (!(condition)) \ + continue; \ + if (len > 3*nb_bits || len > 32) { \ + av_log(NULL, AV_LOG_ERROR, "Too long VLC (%u) in init_vlc\n", len);\ + if (buf != localbuf) \ + av_free(buf); \ + return AVERROR(EINVAL); \ + } \ + buf[j].bits = len; \ + GET_DATA(buf[j].code, codes, i, codes_wrap, codes_size); \ + if (buf[j].code >= (1LL< nb_bits); + // qsort is the slowest part of init_vlc, and could probably be improved or avoided + AV_QSORT(buf, j, struct VLCcode, compare_vlcspec); + COPY(len && len <= nb_bits); + nb_codes = j; + + return vlc_common_end(vlc, nb_bits, nb_codes, buf, + flags, localbuf); +} + +int ff_init_vlc_from_lengths(VLC *vlc, int nb_bits, int nb_codes, + const int8_t *lens, int lens_wrap, + const void *symbols, int symbols_wrap, int symbols_size, + int offset, int flags, void *logctx) +{ + VLCcode localbuf[LOCALBUF_ELEMS], *buf = localbuf; + uint64_t code; + int ret, j, len_max = FFMIN(32, 3 * nb_bits); + + ret = vlc_common_init(vlc, nb_bits, nb_codes, &buf, flags); + if (ret < 0) + return ret; + + j = code = 0; + for (int i = 0; i < nb_codes; i++, lens += lens_wrap) { + int len = *lens; + if (len > 0) { + unsigned sym; + + buf[j].bits = len; + if (symbols) + GET_DATA(sym, symbols, i, symbols_wrap, symbols_size) + else + sym = i; + buf[j].symbol = sym + offset; + buf[j++].code = code; + } else if (len < 0) { + len = -len; + } else + continue; + if (len > len_max || code & ((1U << (32 - len)) - 1)) { + av_log(logctx, AV_LOG_ERROR, "Invalid VLC (length %u)\n", len); + goto fail; + } + code += 1U << (32 - len); + if (code > UINT32_MAX + 1ULL) { + av_log(logctx, AV_LOG_ERROR, "Overdetermined VLC tree\n"); + goto fail; + } + } + return vlc_common_end(vlc, nb_bits, j, buf, flags, localbuf); +fail: + if (buf != localbuf) + av_free(buf); + return AVERROR_INVALIDDATA; +} + +void ff_free_vlc(VLC *vlc) +{ + av_freep(&vlc->table); +}