From patchwork Fri Nov 20 07:20:08 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Rheinhardt X-Patchwork-Id: 23846 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 DB7ED4492D7 for ; Fri, 20 Nov 2020 09:41:39 +0200 (EET) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id AE00668BC7E; Fri, 20 Nov 2020 09:26:07 +0200 (EET) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from mail-ej1-f67.google.com (mail-ej1-f67.google.com [209.85.218.67]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 5664E68BC11 for ; Fri, 20 Nov 2020 09:25:46 +0200 (EET) Received: by mail-ej1-f67.google.com with SMTP id i19so11474206ejx.9 for ; Thu, 19 Nov 2020 23:25:46 -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=5PMeuqZ2ypZO0P8/HOROdeTkh8NnEtLUsES3rOIaxa8=; b=YYHd1Nm7tWuAF1k6Xqa5wISGIgBwB4KWIiaZ4B+OkMof+wB8vfje1ZV82xNYiEzyJg Gl+RBcZCiPU6kqLraWr0nqXFQfXIhtXlpcwCghib/nwV4LYgNl5V9tbhdtJAf6uQd6R9 rGBKNoUDmKgBsTZ4/XK6axd/xOZXrwfdw39KZU/LMexPuneWNw5Fh+DyFIqo3meLh3Hu 9wR1u4zCDcAc/t7nV54/gSNR74/Z3EkEFGNUKskWxtcp2HYZ0AQXLJWvRyJewfEHl/XM J+l8CFhmG87u4xJTZkwgyOv8gHNc1H5J69cDF/DOCOTKEAc43RfQWcz8/cEI+vN0QAvt ZFfA== 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=5PMeuqZ2ypZO0P8/HOROdeTkh8NnEtLUsES3rOIaxa8=; b=Iaslsv6VeK9AEGv4nDNoM5wJaWMqG/PVi/Z3FNwdvC9ZQo3rk/YxTVBQtmz091SwhE B60BUNfj+wUXDSyaixZ7XO01meBxntKlRWs1WGBSV+QumCdZ8q9RIH0NCYQ8kY/GzJ02 qJB95iFGy7c7QzH+7PP2GBzWyssA7LCkNPSOUNpU11xXZUU8fueEn1gpyQHcUwkokEuX VcilZGRVrrMFygB4DVFG9rKnQZIta1wh4bcyDpKLuyUrUmZ0u+x3KwTSeIB5fR4heGmI oP17jV+oSjw2W5LpQOZfnXGqGt7/9/PL6W9iDh6ThKWGaCsYsHwEGpd0pwaUIXU1Waot y8aA== X-Gm-Message-State: AOAM532H6n+LSD4XVlcEjTQ/GU7CvXQYoaTuXijFRKrN5CNs0E0aSEEM vyPsXsxfz0MJZyb+pgF9xPisj+CN4/uViA== X-Google-Smtp-Source: ABdhPJyGM15PPfpeiP5E72CpcHB2t7Q0sSExENV520OsrgvrmhxK3wDGIQAT5G2thp30q/WqzltL1g== X-Received: by 2002:a17:906:13cd:: with SMTP id g13mr33376869ejc.394.1605857145287; Thu, 19 Nov 2020 23:25:45 -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.25.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 19 Nov 2020 23:25:44 -0800 (PST) From: Andreas Rheinhardt To: ffmpeg-devel@ffmpeg.org Date: Fri, 20 Nov 2020 08:20:08 +0100 Message-Id: <20201120072116.818090-96-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 095/162] avcodec/atrac3plus: Run-length encode length tables to make them smaller 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" This is very beneficial for the scale factor tables where 4*64+4*15 bytes of length information can be replaced by eight codebooks of 12 bytes each; furthermore the number of codes as well as the maximum length of a code can be easily derived from said codebooks, making tables containing said information superfluous. This and combining the symbols into one big array also made an array of pointers to the tables redundant. For the wordlen and code table tables the benefits are not that big (given these tables don't contain that many elements), but all in all using codebooks is also advantageouos for them. Therefore it has been done. Signed-off-by: Andreas Rheinhardt --- libavcodec/atrac3plus.c | 55 ++---------- libavcodec/atrac3plus_data.h | 157 +++++++++++++++-------------------- 2 files changed, 76 insertions(+), 136 deletions(-) diff --git a/libavcodec/atrac3plus.c b/libavcodec/atrac3plus.c index 984b06fbe4..3a0a0d5f36 100644 --- a/libavcodec/atrac3plus.c +++ b/libavcodec/atrac3plus.c @@ -78,55 +78,18 @@ av_cold void ff_atrac3p_init_vlcs(void) int i, tab_offset = 0; const uint8_t *xlats; - static const uint8_t wl_nb_bits[4] = { 2, 3, 5, 5 }; - static const uint8_t wl_nb_codes[4] = { 3, 5, 8, 8 }; - static const uint8_t (*const wl_huffs[4])[2] = { - atrac3p_wl_huff1, atrac3p_wl_huff2, - atrac3p_wl_huff3, atrac3p_wl_huff4 - }; - - static const uint8_t ct_nb_bits[4] = { 3, 4, 4, 4 }; - static const uint8_t ct_nb_codes[4] = { 4, 8, 8, 8 }; - static const uint8_t (*const ct_huffs[4])[2] = { - atrac3p_ct_huff1, atrac3p_ct_huff2, - atrac3p_ct_huff3, atrac3p_ct_huff4 - }; - - static const uint8_t sf_nb_bits[8] = { 9, 9, 9, 9, 6, 6, 7, 7 }; - static const uint8_t sf_nb_codes[8] = { 64, 64, 64, 64, 15, 15, 15, 15 }; - static const uint8_t (*const sf_huffs[8])[2] = { - atrac3p_sf_huff1, atrac3p_sf_huff2, atrac3p_sf_huff3, - atrac3p_sf_huff4, atrac3p_sf_huff5, atrac3p_sf_huff6, - atrac3p_sf_huff7, atrac3p_sf_huff8 - }; - + xlats = atrac3p_wl_ct_xlats; for (int i = 0; i < 4; i++) { - wl_vlc_tabs[i].table = &tables_data[tab_offset]; - wl_vlc_tabs[i].table_allocated = 1 << wl_nb_bits[i]; - tab_offset += 1 << wl_nb_bits[i]; - ff_init_vlc_from_lengths(&wl_vlc_tabs[i], wl_nb_bits[i], wl_nb_codes[i], - &wl_huffs[i][0][1], 2, - &wl_huffs[i][0][0], 2, 1, - 0, INIT_VLC_USE_NEW_STATIC, NULL); - - ct_vlc_tabs[i].table = &tables_data[tab_offset]; - ct_vlc_tabs[i].table_allocated = 1 << ct_nb_bits[i]; - tab_offset += 1 << ct_nb_bits[i]; - ff_init_vlc_from_lengths(&ct_vlc_tabs[i], ct_nb_bits[i], ct_nb_codes[i], - &ct_huffs[i][0][1], 2, - &ct_huffs[i][0][0], 2, 1, - 0, INIT_VLC_USE_NEW_STATIC, NULL); + build_canonical_huff(atrac3p_wl_cbs[i], &xlats, + &tab_offset, &wl_vlc_tabs[i]); + build_canonical_huff(atrac3p_ct_cbs[i], &xlats, + &tab_offset, &ct_vlc_tabs[i]); } - for (int i = 0; i < 8; i++) { - sf_vlc_tabs[i].table = &tables_data[tab_offset]; - sf_vlc_tabs[i].table_allocated = 1 << sf_nb_bits[i]; - tab_offset += 1 << sf_nb_bits[i]; - ff_init_vlc_from_lengths(&sf_vlc_tabs[i], sf_nb_bits[i], sf_nb_codes[i], - &sf_huffs[i][0][1], 2, - &sf_huffs[i][0][0], 2, 1, - 0, INIT_VLC_USE_NEW_STATIC, NULL); - } + xlats = atrac3p_sf_xlats; + for (int i = 0; i < 8; i++) + build_canonical_huff(atrac3p_sf_cbs[i], &xlats, + &tab_offset, &sf_vlc_tabs[i]); /* build huffman tables for spectrum decoding */ xlats = atrac3p_spectra_xlats; diff --git a/libavcodec/atrac3plus_data.h b/libavcodec/atrac3plus_data.h index 6b9109cb70..7039936ba3 100644 --- a/libavcodec/atrac3plus_data.h +++ b/libavcodec/atrac3plus_data.h @@ -27,106 +27,83 @@ #include /** VLC tables for wordlen */ -static const uint8_t atrac3p_wl_huff1[3][2] = { - { 0, 1 }, { 1, 2 }, { 7, 2 }, +static const uint8_t atrac3p_wl_cbs[][12] = { + { 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + { 1, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + { 1, 0, 2, 3, 2, 0, 0, 0, 0, 0, 0, 0 }, + { 1, 0, 2, 3, 2, 0, 0, 0, 0, 0, 0, 0 }, }; -static const uint8_t atrac3p_wl_huff2[5][2] = { - { 0, 1 }, { 1, 3 }, { 2, 3 }, { 6, 3 }, { 7, 3 }, -}; - -static const uint8_t atrac3p_wl_huff3[8][2] = { - { 0, 1 }, { 1, 3 }, { 7, 3 }, { 2, 4 }, { 5, 4 }, { 6, 4 }, { 3, 5 }, - { 4, 5 }, +/** VLC tables for code table indexes */ +static const uint8_t atrac3p_ct_cbs[][12] = { + { 1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, + { 0, 1, 5, 2, 0, 0, 0, 0, 0, 0, 0, 0 }, + { 0, 1, 5, 2, 0, 0, 0, 0, 0, 0, 0, 0 }, + { 1, 0, 1, 6, 0, 0, 0, 0, 0, 0, 0, 0 }, }; - -static const uint8_t atrac3p_wl_huff4[8][2] = { - { 0, 1 }, { 1, 3 }, { 7, 3 }, { 2, 4 }, { 3, 4 }, { 6, 4 }, { 4, 5 }, - { 5, 5 }, +/* Symbols for wordlen interleaved with symbols for code table */ +static const uint8_t atrac3p_wl_ct_xlats[] = { + /* wordlen table 1 - 3 entries */ + 0, 1, 7, + /* code table 1 - 4 entries */ + 0, 1, 2, 3, + /* wordlen table 2 - 5 entries */ + 0, 1, 2, 6, 7, + /* code table 2 - 8 entries */ + 0, 1, 2, 3, 4, 5, 6, 7, + /* wordlen table 3 - 8 entries */ + 0, 1, 7, 2, 5, 6, 3, 4, + /* code table 3 - 8 entries */ + 0, 1, 2, 3, 6, 7, 4, 5, + /* wordlen table 4 - 8 entries */ + 0, 1, 7, 2, 3, 6, 4, 5, + /* code table 4 - 8 entries */ + 0, 1, 2, 3, 4, 5, 6, 7, }; /** VLC tables for scale factor indexes */ -static const uint8_t atrac3p_sf_huff1[64][2] = { - { 0, 2 }, { 1, 3 }, { 61, 3 }, { 62, 3 }, { 63, 3 }, { 2, 4 }, - { 60, 4 }, { 3, 8 }, { 4, 8 }, { 5, 8 }, { 6, 8 }, { 57, 8 }, - { 58, 8 }, { 59, 8 }, { 7, 9 }, { 8, 9 }, { 9, 9 }, { 10, 9 }, - { 11, 9 }, { 12, 9 }, { 13, 9 }, { 14, 9 }, { 15, 9 }, { 16, 9 }, - { 17, 9 }, { 18, 9 }, { 19, 9 }, { 20, 9 }, { 21, 9 }, { 22, 9 }, - { 23, 9 }, { 24, 9 }, { 25, 9 }, { 26, 9 }, { 27, 9 }, { 28, 9 }, - { 29, 9 }, { 30, 9 }, { 31, 9 }, { 32, 9 }, { 33, 9 }, { 34, 9 }, - { 35, 9 }, { 36, 9 }, { 37, 9 }, { 38, 9 }, { 39, 9 }, { 40, 9 }, - { 41, 9 }, { 42, 9 }, { 43, 9 }, { 44, 9 }, { 45, 9 }, { 46, 9 }, - { 47, 9 }, { 48, 9 }, { 49, 9 }, { 50, 9 }, { 51, 9 }, { 52, 9 }, - { 53, 9 }, { 54, 9 }, { 55, 9 }, { 56, 9 }, -}; - -static const uint8_t atrac3p_sf_huff2[64][2] = { - { 0, 2 }, { 1, 3 }, { 2, 3 }, { 62, 3 }, { 63, 3 }, { 3, 4 }, - { 61, 4 }, { 4, 8 }, { 5, 8 }, { 6, 8 }, { 57, 8 }, { 58, 8 }, - { 59, 8 }, { 60, 8 }, { 7, 9 }, { 8, 9 }, { 9, 9 }, { 10, 9 }, - { 11, 9 }, { 12, 9 }, { 13, 9 }, { 14, 9 }, { 15, 9 }, { 16, 9 }, - { 17, 9 }, { 18, 9 }, { 19, 9 }, { 20, 9 }, { 21, 9 }, { 22, 9 }, - { 23, 9 }, { 24, 9 }, { 25, 9 }, { 26, 9 }, { 27, 9 }, { 28, 9 }, - { 29, 9 }, { 30, 9 }, { 31, 9 }, { 32, 9 }, { 33, 9 }, { 34, 9 }, - { 35, 9 }, { 36, 9 }, { 37, 9 }, { 38, 9 }, { 39, 9 }, { 40, 9 }, - { 41, 9 }, { 42, 9 }, { 43, 9 }, { 44, 9 }, { 45, 9 }, { 46, 9 }, - { 47, 9 }, { 48, 9 }, { 49, 9 }, { 50, 9 }, { 51, 9 }, { 52, 9 }, - { 53, 9 }, { 54, 9 }, { 55, 9 }, { 56, 9 }, -}; - -static const uint8_t atrac3p_sf_huff3[64][2] = { - { 0, 1 }, { 1, 3 }, { 63, 3 }, { 2, 5 }, { 3, 5 }, { 61, 5 }, - { 62, 5 }, { 4, 7 }, { 60, 7 }, { 59, 8 }, { 5, 9 }, { 6, 9 }, - { 7, 9 }, { 8, 9 }, { 9, 9 }, { 10, 9 }, { 11, 9 }, { 12, 9 }, - { 13, 9 }, { 14, 9 }, { 15, 9 }, { 16, 9 }, { 17, 9 }, { 18, 9 }, - { 19, 9 }, { 20, 9 }, { 21, 9 }, { 22, 9 }, { 23, 9 }, { 24, 9 }, - { 25, 9 }, { 26, 9 }, { 27, 9 }, { 28, 9 }, { 29, 9 }, { 30, 9 }, - { 31, 9 }, { 32, 9 }, { 33, 9 }, { 34, 9 }, { 35, 9 }, { 36, 9 }, - { 37, 9 }, { 38, 9 }, { 39, 9 }, { 40, 9 }, { 41, 9 }, { 42, 9 }, - { 43, 9 }, { 44, 9 }, { 45, 9 }, { 46, 9 }, { 47, 9 }, { 48, 9 }, - { 49, 9 }, { 50, 9 }, { 51, 9 }, { 52, 9 }, { 53, 9 }, { 54, 9 }, - { 55, 9 }, { 56, 9 }, { 57, 9 }, { 58, 9 }, -}; - -static const uint8_t atrac3p_sf_huff4[64][2] = { - { 0, 2 }, { 1, 3 }, { 2, 3 }, { 62, 3 }, { 63, 3 }, { 3, 5 }, - { 4, 5 }, { 60, 5 }, { 61, 5 }, { 5, 7 }, { 58, 7 }, { 59, 7 }, - { 6, 9 }, { 7, 9 }, { 8, 9 }, { 9, 9 }, { 10, 9 }, { 11, 9 }, - { 12, 9 }, { 13, 9 }, { 14, 9 }, { 15, 9 }, { 16, 9 }, { 17, 9 }, - { 18, 9 }, { 19, 9 }, { 20, 9 }, { 21, 9 }, { 22, 9 }, { 23, 9 }, - { 24, 9 }, { 25, 9 }, { 26, 9 }, { 27, 9 }, { 28, 9 }, { 29, 9 }, - { 30, 9 }, { 31, 9 }, { 32, 9 }, { 33, 9 }, { 34, 9 }, { 35, 9 }, - { 36, 9 }, { 37, 9 }, { 38, 9 }, { 39, 9 }, { 40, 9 }, { 41, 9 }, - { 42, 9 }, { 43, 9 }, { 44, 9 }, { 45, 9 }, { 46, 9 }, { 47, 9 }, - { 48, 9 }, { 49, 9 }, { 50, 9 }, { 51, 9 }, { 52, 9 }, { 53, 9 }, - { 54, 9 }, { 55, 9 }, { 56, 9 }, { 57, 9 }, -}; - -static const uint8_t atrac3p_sf_huff5[15][2] = { - { 0, 2 }, { 1, 3 }, { 13, 3 }, { 14, 3 }, { 15, 3 }, { 2, 4 }, - { 12, 4 }, { 3, 6 }, { 4, 6 }, { 5, 6 }, { 6, 6 }, { 7, 6 }, - { 9, 6 }, { 10, 6 }, { 11, 6 }, +static const uint8_t atrac3p_sf_cbs[][12] = { + { 0, 1, 4, 2, 0, 0, 0, 7, 50, 0, 0, 0 }, + { 0, 1, 4, 2, 0, 0, 0, 7, 50, 0, 0, 0 }, + { 1, 0, 2, 0, 4, 0, 2, 1, 54, 0, 0, 0 }, + { 0, 1, 4, 0, 4, 0, 3, 0, 52, 0, 0, 0 }, + { 0, 1, 4, 2, 0, 8, 0, 0, 0, 0, 0, 0 }, + { 0, 1, 4, 2, 0, 8, 0, 0, 0, 0, 0, 0 }, + { 1, 0, 2, 2, 2, 0, 8, 0, 0, 0, 0, 0 }, + { 0, 1, 4, 2, 2, 2, 4, 0, 0, 0, 0, 0 }, }; -static const uint8_t atrac3p_sf_huff6[15][2] = { - { 0, 2 }, { 1, 3 }, { 2, 3 }, { 14, 3 }, { 15, 3 }, { 3, 4 }, - { 13, 4 }, { 4, 6 }, { 5, 6 }, { 6, 6 }, { 7, 6 }, { 9, 6 }, - { 10, 6 }, { 11, 6 }, { 12, 6 }, +static const uint8_t atrac3p_sf_xlats[] = { + /* Scale factor index 1 - 64 entries */ + 0, 1, 61, 62, 63, 2, 60, 3, 4, 5, 6, 57, 58, 59, 7, 8, + 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, + 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, + 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, + /* Scale factor index 2 - 64 entries */ + 0, 1, 2, 62, 63, 3, 61, 4, 5, 6, 57, 58, 59, 60, 7, 8, + 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, + 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, + 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, + /* Scale factor index 3 - 64 entries */ + 0, 1, 63, 2, 3, 61, 62, 4, 60, 59, 5, 6, 7, 8, 9, 10, + 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, + 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, + 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, + /* Scale factor index 4 - 64 entries */ + 0, 1, 2, 62, 63, 3, 4, 60, 61, 5, 58, 59, 6, 7, 8, 9, + 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, + 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, + 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, + /* Scale factor index 5 - 15 entries */ + 0, 1, 13, 14, 15, 2, 12, 3, 4, 5, 6, 7, 9, 10, 11, + /* Scale factor index 6 - 15 entries */ + 0, 1, 2, 14, 15, 3, 13, 4, 5, 6, 7, 9, 10, 11, 12, + /* Scale factor index 7 - 15 entries */ + 0, 1, 15, 2, 14, 3, 13, 4, 5, 6, 7, 9, 10, 11, 12, + /* Scale factor index 8 - 15 entries */ + 0, 1, 2, 14, 15, 3, 13, 4, 12, 5, 11, 6, 7, 9, 10, }; -static const uint8_t atrac3p_sf_huff7[15][2] = { - { 0, 1 }, { 1, 3 }, { 15, 3 }, { 2, 4 }, { 14, 4 }, { 3, 5 }, - { 13, 5 }, { 4, 7 }, { 5, 7 }, { 6, 7 }, { 7, 7 }, { 9, 7 }, - { 10, 7 }, { 11, 7 }, { 12, 7 }, -}; - -static const uint8_t atrac3p_sf_huff8[15][2] = { - { 0, 2 }, { 1, 3 }, { 2, 3 }, { 14, 3 }, { 15, 3 }, { 3, 4 }, - { 13, 4 }, { 4, 5 }, { 12, 5 }, { 5, 6 }, { 11, 6 }, { 6, 7 }, - { 7, 7 }, { 9, 7 }, { 10, 7 }, -}; - -/** VLC tables for code table indexes */ static const uint8_t atrac3p_ct_huff1[4][2] = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 3, 3 }, };