Re: [Cbor] Interactions of packed CBOR and tags

Brendan Moran <Brendan.Moran@arm.com> Thu, 03 September 2020 17:06 UTC

Return-Path: <Brendan.Moran@arm.com>
X-Original-To: cbor@ietfa.amsl.com
Delivered-To: cbor@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 036203A110F for <cbor@ietfa.amsl.com>; Thu, 3 Sep 2020 10:06:14 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_MSPIKE_H2=-0.001, SPF_PASS=-0.001, UNPARSEABLE_RELAY=0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=armh.onmicrosoft.com header.b=hgg8usoO; dkim=pass (1024-bit key) header.d=armh.onmicrosoft.com header.b=hgg8usoO
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id f4MKy9FwP3SX for <cbor@ietfa.amsl.com>; Thu, 3 Sep 2020 10:06:11 -0700 (PDT)
Received: from EUR05-AM6-obe.outbound.protection.outlook.com (mail-am6eur05on2066.outbound.protection.outlook.com [40.107.22.66]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 027333A10CA for <cbor@ietf.org>; Thu, 3 Sep 2020 10:06:10 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=958ksVG3mLWeelWHJD2KUUUZySUd3TWgn4qo1q6trns=; b=hgg8usoOn1NS3OoipjhROniarAVw80XPVqc//h99fOwM7R3mz072tOAeYE+mclyhtvXIJMdCu6OkT1LRe+Y8EzzvgTEp0XuFXvivG+ng1jHkALyVbqaL2SC5S6MQCx+1ZKIRsv5osUsXctqesKFZhdTolgbMomv4HjQ2npXcI7Q=
Received: from AM6PR10CA0010.EURPRD10.PROD.OUTLOOK.COM (2603:10a6:209:89::23) by HE1PR0801MB1865.eurprd08.prod.outlook.com (2603:10a6:3:4f::21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3348.15; Thu, 3 Sep 2020 17:06:08 +0000
Received: from AM5EUR03FT045.eop-EUR03.prod.protection.outlook.com (2603:10a6:209:89:cafe::78) by AM6PR10CA0010.outlook.office365.com (2603:10a6:209:89::23) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3348.15 via Frontend Transport; Thu, 3 Sep 2020 17:06:07 +0000
X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 63.35.35.123) smtp.mailfrom=arm.com; ietf.org; dkim=pass (signature was verified) header.d=armh.onmicrosoft.com;ietf.org; dmarc=bestguesspass action=none header.from=arm.com;
Received-SPF: Pass (protection.outlook.com: domain of arm.com designates 63.35.35.123 as permitted sender) receiver=protection.outlook.com; client-ip=63.35.35.123; helo=64aa7808-outbound-1.mta.getcheckrecipient.com;
Received: from 64aa7808-outbound-1.mta.getcheckrecipient.com (63.35.35.123) by AM5EUR03FT045.mail.protection.outlook.com (10.152.17.105) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3326.19 via Frontend Transport; Thu, 3 Sep 2020 17:06:06 +0000
Received: ("Tessian outbound a0bffebca527:v64"); Thu, 03 Sep 2020 17:06:06 +0000
X-CheckRecipientChecked: true
X-CR-MTA-CID: 404254267ef68eff
X-CR-MTA-TID: 64aa7808
Received: from dcc4c8ffc171.1 by 64aa7808-outbound-1.mta.getcheckrecipient.com id 351BF2B7-B352-4F04-9462-CA39DF2CD4CA.1; Thu, 03 Sep 2020 17:06:01 +0000
Received: from EUR03-DB5-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id dcc4c8ffc171.1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Thu, 03 Sep 2020 17:06:01 +0000
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=KMmCCk3jOX8NRptgKMr1oGIWRvEQ9JADQqdHjx9+NnUsFslOIoDEeemtvpwhgxsB6Sg42XeAb/d12R/ubCWr8GdccZgvQVqQ2YE/mginRbxTg/IHYs/p6rHdNH7D03YcPr9dt+DNJXEybGPwmjabn5dOoi1NZTi2fcNEQAO6zX+TdYg3ZFvP8LQ3ZechE0jPYNKa4nWAeSLoofiYCmNiARlJIPtZOGXJn8OGM04scUeXplcIxh0KJ+QjVkMXFQHxHh2QMMX84hkBtsdcatTPqc2HVTAnlXHuSfSIOe9k4EHNUMrx8sKUCsOh0/4fptc4ymMxVycwLB69sSwWcacviQ==
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-SenderADCheck; bh=958ksVG3mLWeelWHJD2KUUUZySUd3TWgn4qo1q6trns=; b=bnjcO41aZBe9F/zRRZBDZkCbpqQvdK5lToG997YwhyMtEtHtWWmpv0sYu5etnYAS6EFzvHBLOKQECNFg0B5+L/cPXwFkCu0Q+iPDMKTNbg1PmCW8CEfZvW1cH6bJ9MqKtaQZq+GGlri+qN0obB3G5a6LPNzzdxbwFP0fnqwX6wdhm4US/v90eOqZqAs+zuhNkiza8T+kRQBb26QZ67/waF631zEFwHGmAzUlFaFrT2lYWi5rAxQmUzCI+Yvz176AiGzKMbH4Yo03RrEInPwlsxWIb5vVAOpwuITscEkWm0sxELuBXy8mAhbYvdk9yr1/x4S2ArXbUEHMB+UQswZFoA==
ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=arm.com; dmarc=pass action=none header.from=arm.com; dkim=pass header.d=arm.com; arc=none
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=958ksVG3mLWeelWHJD2KUUUZySUd3TWgn4qo1q6trns=; b=hgg8usoOn1NS3OoipjhROniarAVw80XPVqc//h99fOwM7R3mz072tOAeYE+mclyhtvXIJMdCu6OkT1LRe+Y8EzzvgTEp0XuFXvivG+ng1jHkALyVbqaL2SC5S6MQCx+1ZKIRsv5osUsXctqesKFZhdTolgbMomv4HjQ2npXcI7Q=
Received: from AM6PR08MB4738.eurprd08.prod.outlook.com (2603:10a6:20b:cf::10) by AM6PR08MB5237.eurprd08.prod.outlook.com (2603:10a6:20b:e9::11) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3348.15; Thu, 3 Sep 2020 17:05:55 +0000
Received: from AM6PR08MB4738.eurprd08.prod.outlook.com ([fe80::a98d:5ebe:dc1d:ea56]) by AM6PR08MB4738.eurprd08.prod.outlook.com ([fe80::a98d:5ebe:dc1d:ea56%3]) with mapi id 15.20.3348.016; Thu, 3 Sep 2020 17:05:55 +0000
From: Brendan Moran <Brendan.Moran@arm.com>
To: Carsten Bormann <cabo@tzi.org>
CC: Jim Schaad <ietf@augustcellars.com>, "cbor@ietf.org" <cbor@ietf.org>
Thread-Topic: [Cbor] Interactions of packed CBOR and tags
Thread-Index: AdZ8s0xpKERBvw7yTZyxz2a31flriAABj4uAAAP6fwABR/KiAAAIntwAAAHAYYAAAG2GAA==
Date: Thu, 3 Sep 2020 17:05:54 +0000
Message-ID: <6ED2C94E-CA4D-4D11-87FA-0E8010690A69@arm.com>
References: <00c101d67cb5$2588b790$709a26b0$@augustcellars.com> <E30F54B6-1A63-48AC-89AE-61983654B5A9@tzi.org> <00cc01d67cc9$766c7b60$63457220$@augustcellars.com> <4AE9B2FA-EEB3-4B45-96E4-9DC85118567D@arm.com> <016f01d6820b$bc7d7cc0$35787640$@augustcellars.com> <62FEE35D-75F3-422E-A6C0-FFE86ACBD9A5@tzi.org>
In-Reply-To: <62FEE35D-75F3-422E-A6C0-FFE86ACBD9A5@tzi.org>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-mailer: Apple Mail (2.3608.120.23.2.1)
Authentication-Results-Original: tzi.org; dkim=none (message not signed) header.d=none;tzi.org; dmarc=none action=none header.from=arm.com;
x-originating-ip: [82.20.19.206]
x-ms-publictraffictype: Email
X-MS-Office365-Filtering-HT: Tenant
X-MS-Office365-Filtering-Correlation-Id: 6759b52b-796a-46f8-c0e1-08d8502ba5e9
x-ms-traffictypediagnostic: AM6PR08MB5237:|HE1PR0801MB1865:
X-Microsoft-Antispam-PRVS: <HE1PR0801MB18655E0C4FC2B18046327F81EA2C0@HE1PR0801MB1865.eurprd08.prod.outlook.com>
x-checkrecipientrouted: true
nodisclaimer: true
x-ms-oob-tlc-oobclassifiers: OLM:10000;OLM:10000;
X-MS-Exchange-SenderADCheck: 1
X-Microsoft-Antispam-Untrusted: BCL:0;
X-Microsoft-Antispam-Message-Info-Original: EpTcyKOzjOyJoVtF1zfDEfwjd1oFdJbH3VTa6mlQ9UNuVWNyqgF/p0tQ+wEAkSdKHDsoahYQAjzgcunruB1EjVmV9AclEhgEjX49HIeBvCoHiJIkZeb1ubwWVuARKOy1AOFOciIwkVlTA5MzKxbxpJGUVK2JppLvZ50VIs0u3uM8i+ayOtbyupxLbMdgptIT9/Z4gV+pHBr8yWtMPhU5Zg0F92v49xp4IzLPcrSN6Q23NFsJOtRuTpRKLnahsoFZbGLz44ExQpfkmRm5wB1c42Cn3+XKMfVum/vowQHFsnWBFNvFwJajGaEuPxZE1urbZt3izerQqw1I5GhC6L7rmMivZgk+7zg3fwIKfXLfQe6zD0DgYing6Vpc2PVK+mV9bktRhHDLaDrTi//FJYyGmw==
X-Forefront-Antispam-Report-Untrusted: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:AM6PR08MB4738.eurprd08.prod.outlook.com; PTR:; CAT:NONE; SFS:(4636009)(39860400002)(396003)(366004)(346002)(376002)(136003)(966005)(5660300002)(6506007)(8936002)(53546011)(2616005)(316002)(186003)(6916009)(478600001)(86362001)(4326008)(26005)(2906002)(6512007)(91956017)(66946007)(76116006)(8676002)(66556008)(64756008)(83380400001)(36756003)(71200400001)(54906003)(6486002)(66476007)(33656002)(66446008); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: g8m/3eATvB1LpMljzDJQtzqqApnpINiJf91F2QsQfe/FIXw0Ql+I/suM4us2LgY0TXscGN3QSj2Pex11VUnSQrGEQ0uIJsyTKtZeKUYb+vhZV2mo6+coV3gCpK8nS6ecVRKCKQkVgruhGTQK2euT5a4mtKAWvPwY/Zi1ZqB16HCVHjygLY+7X2yuoAZI+mqZdzf5xPaS6KxiE2CKbcov9LCbqOeetNF19IUxhn5SVpFmjBIh4zn0jfaoxlUgC0BVjk4JJRvjO4SlbH9uvbL8mtWbs8o+fwJpbZ16+rgV9mBye3FDsAQNRXXBSSUjVAgbxgmfTA5hTiyF+FYLXInUKHyIsEhE1mV9WYTjxxFFfUCFPQlMOoXWIeeM0CnyiDV6HVq/mI7Sr7kCUcfbogpp52XAvgD1SX7Ne9o8QicCN9RCmPwvKBYdFV8S31YHt/4L9JDtkzc1YOmoww/m7sdOoAbNjwbYGzyOyoYRqiXBJR/YVGDsMgGI8+rD2NrCm6B1y+PhcBWGoeDHQLStEODP5nFa2FkP5HBzEjBpYn+7dsOnUEhInxYmaaeQxjDQxYjuaUFTQH7XKf8ekBwez0g8bwRCyWpZxggXEzdsiWXysVqYvZpInYlqVY5D9lnOlF6nSG/0+ymHQuId0Cf5pkr7tA==
x-ms-exchange-transport-forked: True
Content-Type: text/plain; charset="utf-8"
Content-ID: <76B20F6BE182244C8BE524038D4AB039@eurprd08.prod.outlook.com>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR08MB5237
Original-Authentication-Results: tzi.org; dkim=none (message not signed) header.d=none;tzi.org; dmarc=none action=none header.from=arm.com;
X-EOPAttributedMessage: 0
X-MS-Exchange-Transport-CrossTenantHeadersStripped: AM5EUR03FT045.eop-EUR03.prod.protection.outlook.com
X-MS-Office365-Filtering-Correlation-Id-Prvs: 14301b99-8605-4239-30f5-08d8502b9edc
X-Microsoft-Antispam: BCL:0;
X-Microsoft-Antispam-Message-Info: sXnK95zyGV8XqQ3J5T6WEiCL8idJJBgly0x8klrpBvCoWll0JBDwRGcw3YUpis5pf4q/pGzFYfcG4VAT471MSa4I3Zj02Tdiy5mW2iubkogkKO2LaXa5CDvI0jkK7L5b6jXloeDgmCqC3dYW6j6Np9bb+CX2blS6vizbI3fG2Feyp3m9CTgATXluSQLpc3kqu1HGq5isLkC9dC0sFqBhBhrWK0n9R9S8X0Q8uSPsg53Na37eFbKs74yMe7+CqYIlnPz7nfjVQF4qj4VJEPuIGqaGvXrfmKJ5G2a+606nAh0QHwUqJP00IqclQgSaLBNVRmUWSFntN7xCaLv1rshHxmg4YzU5sOPBYNIT/+sm2AGpgqnuj7UmGJghvmz4QeE0vLgpzbia18V4yKzr/sOV+1gpOubNb8qG72XE0Tz2OeJR6upCSg4Tm8tBQTbhsCxuXD+DdbIZ4t3nlEIe53H0jdh8dTz3DCRfESW+o4Yw5oE=
X-Forefront-Antispam-Report: CIP:63.35.35.123; CTRY:IE; LANG:en; SCL:1; SRV:; IPV:CAL; SFV:NSPM; H:64aa7808-outbound-1.mta.getcheckrecipient.com; PTR:ec2-63-35-35-123.eu-west-1.compute.amazonaws.com; CAT:NONE; SFS:(4636009)(39860400002)(396003)(136003)(346002)(376002)(46966005)(6486002)(2616005)(5660300002)(4326008)(86362001)(26005)(83380400001)(316002)(6862004)(82310400003)(186003)(336012)(2906002)(36906005)(8676002)(54906003)(53546011)(8936002)(33656002)(6506007)(70206006)(356005)(47076004)(478600001)(70586007)(82740400003)(81166007)(36756003)(6512007)(966005); DIR:OUT; SFP:1101;
X-OriginatorOrg: arm.com
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 03 Sep 2020 17:06:06.9571 (UTC)
X-MS-Exchange-CrossTenant-Network-Message-Id: 6759b52b-796a-46f8-c0e1-08d8502ba5e9
X-MS-Exchange-CrossTenant-Id: f34e5979-57d9-4aaa-ad4d-b122a662184d
X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=f34e5979-57d9-4aaa-ad4d-b122a662184d; Ip=[63.35.35.123]; Helo=[64aa7808-outbound-1.mta.getcheckrecipient.com]
X-MS-Exchange-CrossTenant-AuthSource: AM5EUR03FT045.eop-EUR03.prod.protection.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Anonymous
X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem
X-MS-Exchange-Transport-CrossTenantHeadersStamped: HE1PR0801MB1865
Archived-At: <https://mailarchive.ietf.org/arch/msg/cbor/PIh_JmDw0dQzERx7xrdONU6p-JM>
Subject: Re: [Cbor] Interactions of packed CBOR and tags
X-BeenThere: cbor@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "Concise Binary Object Representation \(CBOR\)" <cbor.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/cbor>, <mailto:cbor-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cbor/>
List-Post: <mailto:cbor@ietf.org>
List-Help: <mailto:cbor-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/cbor>, <mailto:cbor-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 03 Sep 2020 17:06:14 -0000


> On 3 Sep 2020, at 17:53, Carsten Bormann <cabo@tzi.org> wrote:
>
> On 2020-09-03, at 18:03, Jim Schaad <ietf@augustcellars.com> wrote:
>>
>> 6([ "www.", "merch", "datatracker"], [".ietf.org""], 224(225(simple(2))), 224(226(simple(2)))]
>>
>> Where we have pulled both prefix and postfix strings extracted and maximize the amount of commonality.
>
> I like the idea of adding suffix packing.
>
> In the current proposal, to distinguish shared items from prefix packing, we have
>
> — a separate table (and thus number space), which makes sense if prefixes are rarely used as shared items and v.v. (using a prefix as shared item just requires prefixing it to the empty item, though);
> — separate referents (one with no content, one with the content the prefix is prefixed to).
>
> Adding suffix packing, we could have a third table and a third set of referents (also with content).  We also could have just separate referents, sharing the table/number space, if that makes sense.

[BJM] Unless we have a way to obtain a whole new referent space with small values, I think that sharing the table is optimal. This also allows reuse of individual values as either prefixes or postfixes, which should yield some additional compression opportunities. This will be even more interesting in the array space.

> We could also rethink the whole separation of shared items from prefix/suffix items in this process.

[BJM] I’m not sure that will result in the gains we want, since it inflates the reference values on shared items, which sit in a different reference space due to the use of simple values and 6(int) values. However, it might also yield some reduced cross-referencing. I’m not sure how this plays out overall, but my intuition is that 2 tables is better.

>
> As Brendan says, being able to optimize the tables so the frequently used items land in the areas that have short referents is important.
>
> [Apologies for using the term referent, which isn’t even in my dictionaries with the meaning I’m using it for (the thing that references).  But that’s the usage I learned when I learned about them in the 1970s… [1]]
>
> Making prefix/suffix packing well-defined for arrays isn’t hard.  For maps, there is no difference (assuming we are always handling full key/value pairs — just doing a single key or a value can be done by sharing items).
>
> I don’t think we want to address what would be “deterministic packing”.
>
> Grüße, Carsten
>
> [1]: https://scholar.google.com/scholar?hl=en&q=Ross%2C+D.+T.%2C+%22Uniform+Referents%3A+An+Essential+Property+for+a+Software+Engineering+Language.%22+Paper+presented+at+the+3rd+International+Symposium+on+Computer+and+Information+Sciences+%28COINS-69%29%2C+Miami+Beach%2C+Florida%2C+18%2D%2D20+December+19691969.
>
>
> _______________________________________________
> CBOR mailing list
> CBOR@ietf.org
> https://www.ietf.org/mailman/listinfo/cbor

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.