Re: [Cbor] Ordering of items in the prefix table

Brendan Moran <Brendan.Moran@arm.com> Fri, 04 September 2020 15:51 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 8AA693A0D89; Fri, 4 Sep 2020 08:51:21 -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=F/xGJR1Z; dkim=pass (1024-bit key) header.d=armh.onmicrosoft.com header.b=F/xGJR1Z
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 JXbn26zSIKtw; Fri, 4 Sep 2020 08:51:19 -0700 (PDT)
Received: from EUR03-DB5-obe.outbound.protection.outlook.com (mail-eopbgr40062.outbound.protection.outlook.com [40.107.4.62]) (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 3B82E3A0D75; Fri, 4 Sep 2020 08:51:19 -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=vJzRITHi3MHffaKCeEVgNVziPoI4yaT2KQpVCuBlf8U=; b=F/xGJR1ZweGOpj0pPGWpF51ZlrK7qzKGPdJHXDjKwdQrzunnsYVVoshwmHBUMeCfprOF4KAdIjock8QpSZqMwCVvk4PM9AnlelwljKaz+7rS7DRgiXplUOsy75NBaJdVf4wPtfwAptFBTlPucDUCQlFBrYL6SIytwnRPAMdK/5s=
Received: from DB6PR07CA0117.eurprd07.prod.outlook.com (2603:10a6:6:2c::31) by DB7PR08MB3802.eurprd08.prod.outlook.com (2603:10a6:10:77::21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3326.19; Fri, 4 Sep 2020 15:51:15 +0000
Received: from DB5EUR03FT055.eop-EUR03.prod.protection.outlook.com (2603:10a6:6:2c:cafe::86) by DB6PR07CA0117.outlook.office365.com (2603:10a6:6:2c::31) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3370.7 via Frontend Transport; Fri, 4 Sep 2020 15:51:15 +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 DB5EUR03FT055.mail.protection.outlook.com (10.152.21.30) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3348.16 via Frontend Transport; Fri, 4 Sep 2020 15:51:15 +0000
Received: ("Tessian outbound a0bffebca527:v64"); Fri, 04 Sep 2020 15:51:15 +0000
X-CheckRecipientChecked: true
X-CR-MTA-CID: 2f12f295ccc0d9e9
X-CR-MTA-TID: 64aa7808
Received: from d5fe70c7714b.1 by 64aa7808-outbound-1.mta.getcheckrecipient.com id E0BA4DA6-F785-4FF0-887B-28B7645FD6AE.1; Fri, 04 Sep 2020 15:50:50 +0000
Received: from EUR04-HE1-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id d5fe70c7714b.1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Fri, 04 Sep 2020 15:50:50 +0000
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=UeYho8htkO7yP0pLCDfFxEI+5jyfFJDLOBLklYCfhvww62e2Qa7rqv8YcrWWGYtUYzUKOwGWtowi6rwJhZf+Ch+Sq1mAmjLma9QSSE3dMn0FQv7GkjKUmqnO8LxFkYQ3/aelM/NSvIaqCoR7lI/GZKEppCvRKP1nyvK8JIX4b69duX7FXk3N963fKVYpNgpjixN8jt0a6OJX8QW8gNpvv+aF1N7Prk+QWohmgSmz3Vpgsp83lipbv2jGF00fWEwvKBjyVpJLsG7iphdKs3lNSI9gi6YgwUbWNTd/r6u67gA3sw3bruAG3h+A6r4zRFr9bdGxm1ochJ1vcigAl4xaIQ==
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=vJzRITHi3MHffaKCeEVgNVziPoI4yaT2KQpVCuBlf8U=; b=aeWFqYP2HcPlxWppZFRcJb8B1Hu9cdyHIox4xvrVJEsXkiDp+Sk67ymkQTVjB3paVXRGoPMnFLbDvfgNcMQHNnENRoh6HqHTeANwm4IrTlXgj+9izQvECsxBCYLHz3+nLdAHyuCBvJiMtiq+9w5Iqbcrh29MnTv5mGdcVGqDiHOLEw8CVKNHCN+xZaOfEt9bAnU+ZzfgnTxRgc8s83ndmv2behuHKye6qFKQ2vX4kCa9qv5yGrwJlEhvKPIxAGUCz8y0+xFuVdh4VEgwoHMehLusCTKXpfgiBikhYJPXZlnolpWNlGpx68Kylo3kgKIhGb3cZ51/bZ3fL3tVHGMnSA==
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=vJzRITHi3MHffaKCeEVgNVziPoI4yaT2KQpVCuBlf8U=; b=F/xGJR1ZweGOpj0pPGWpF51ZlrK7qzKGPdJHXDjKwdQrzunnsYVVoshwmHBUMeCfprOF4KAdIjock8QpSZqMwCVvk4PM9AnlelwljKaz+7rS7DRgiXplUOsy75NBaJdVf4wPtfwAptFBTlPucDUCQlFBrYL6SIytwnRPAMdK/5s=
Received: from AM6PR08MB4738.eurprd08.prod.outlook.com (2603:10a6:20b:cf::10) by AM6PR08MB4967.eurprd08.prod.outlook.com (2603:10a6:20b:e8::13) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3348.15; Fri, 4 Sep 2020 15:50:47 +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.017; Fri, 4 Sep 2020 15:50:47 +0000
From: Brendan Moran <Brendan.Moran@arm.com>
To: Carsten Bormann <cabo@tzi.org>
CC: Michael Richardson <mcr+ietf@sandelman.ca>, "cbor@ietf.org" <cbor@ietf.org>, Jim Schaad <ietf@augustcellars.com>, "draft-bormann-cbor-packed@ietf.org" <draft-bormann-cbor-packed@ietf.org>
Thread-Topic: [Cbor] Ordering of items in the prefix table
Thread-Index: AdZ8SHGvHcW3bURCSR6HY4XY2dTJLABIBAAAAAAyEgAAB4qYAAAARu4AAVKkkgA=
Date: Fri, 4 Sep 2020 15:50:47 +0000
Message-ID: <9C89B5D9-010A-4E72-AC53-5CC1C2473B84@arm.com>
References: <008d01d67c48$d25c4440$7714ccc0$@augustcellars.com> <29638.1598639086@localhost> <B7320B50-BB7D-4E0C-BA11-E35B69F90867@tzi.org> <17395.1598652378@localhost> <841AA64E-647F-49BF-B760-A6F5041DDC14@tzi.org>
In-Reply-To: <841AA64E-647F-49BF-B760-A6F5041DDC14@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: ed2cf1c8-0522-4b6e-152f-08d850ea5af6
x-ms-traffictypediagnostic: AM6PR08MB4967:|DB7PR08MB3802:
X-Microsoft-Antispam-PRVS: <DB7PR08MB3802F3CEA043E5B0681A9109EA2D0@DB7PR08MB3802.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: TKcWNrCtgYw0JcfcUihvCRPvPCUq4Yt2i5EZ9RDwl1+8H6KrmretXsSEVf2vvpHlpvw+2xlaFB5hpZP4XLHlV+4rZ4BKGgN7xa4cdp0RL3KkEoomxz0JO/oX+Sy3EAc4bAvM2McWXMYHRAO4v7hIgAoeZlJc4jVC/AMVrJioyvxJt8LzItLkhemQt/6XrJfH0MSUjXZ5ZvCO1budAMBb/u44T3mwOeGFgPnOnov+A5+lKU8uLCj+eCzvWTjne+wPEyxKg0nHnwgJB351OShRmQhHBCkQpa/h5WY2g9/TcpMlEak2JF2mgnRAB1ynGDPUz0TAFp1LKjx2PxxM+6gvqShiPnEzuAUgVO0VQQSOQHABYZi6ayDN4WEUD1fm6haEvKIC8qCqkMAQvFgfG5+mfA==
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)(376002)(366004)(39860400002)(396003)(346002)(136003)(186003)(36756003)(2906002)(66446008)(64756008)(66476007)(6916009)(66946007)(6512007)(53546011)(6506007)(26005)(8676002)(71200400001)(76116006)(91956017)(2616005)(66556008)(33656002)(8936002)(86362001)(316002)(6486002)(966005)(83380400001)(4326008)(478600001)(5660300002)(54906003); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: S6Gl538HyR1KypuuiZy2QD1oIXS8Xd0Wgi9mmZJ+61Bs+vrT+xNDLzH10TnCX4pEq5aeobueDktxgxKuE00YJrJ1LO8wYo8P5PYAotg1PeOaF0pyGbw0TTxYzEKLvXLSbcxdWLKeItLRMxopqPmTVTiU/w16+Q0Ls37j/lgYQkf7cuvl78En0Ksd1iD3Hklf1Sg4Pqq53chnaYX9vdeHcAux3W2EKR6Rz+gwV12lZgknGddDNbbKbaUyDS7P8Yz4MC70vSPHWlRMOgQ6uuxK/zlS35ZbCsVX3oazWHCQIKVETMp9KhoBU+qjWHtVZHCeCBpBvsPM311oEodxBMQqz+izD2Yc+BCg5gaaddTxauu+K37SJyi0h6mKJdAYAW+BMiX8mc8fTdGsu+hEsrnpI+yhZm/aQBnTnJXhm65D7k/DTXfSPd7zdLSJ+sYMm2MBMt3Pxaeafl1iim9RSenuxO/yuTcHuzAH2fF8tDvJNRI4X4v5Ip1F+sadRCWic+aSQ+LytBIo5iIpThareXydv9BlylU3JNaJ2WwP1WRzRd3/7+99o4znmAP7xNiDQpMEuWFeD8umcfNGRlphwENSV9UP4QLCHua8AG8l4/YCsoyw1+4/Jpfc7xP/KXbyjz/4JNENsLICbV2bizsM7muyaQ==
x-ms-exchange-transport-forked: True
Content-Type: text/plain; charset="utf-8"
Content-ID: <2ADED8167119BB4F9BBD56113121CE57@eurprd08.prod.outlook.com>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR08MB4967
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: DB5EUR03FT055.eop-EUR03.prod.protection.outlook.com
X-MS-Office365-Filtering-Correlation-Id-Prvs: 23010e73-0877-429c-aa72-08d850ea4aaa
X-Microsoft-Antispam: BCL:0;
X-Microsoft-Antispam-Message-Info: YHqwIFCqDbQEYcJCFbHewzSCKYBxibzWD8uoO7n09zvzF9Bmty4dg/JrFMBz8LWERwyfVQlPjZxb7CkN2HoxIuqQ/kfQ+c+s3Lj4CYjsrEG/uAycKJAExeMpLYKU55ApePiG77ki2dCCbWVYPQYs3dZlmZpv1Rbt6IoDVjCucNFnGqmgJsWh2RJ0USu/Q0y2agtQboLM6r2BshsM9DbrCJaNczH8ppcMhYuEwxBp5q1BUGmwXFnSW7HZ6al5i2TyDljYdK8nAHZqiZqTPFV2mkA6OE/B9KcMR0oJmgus9jEJSrYooYJDKN199rmmFXHRS5mJAaQ30x0JZqKVKWUNMWL4egX3i1ISpkD2+4FYR1IkYID8yv6AhxcsWgBWPAu4pLO/9/3EoQVB9QWDXkrMxU5lm3fJXaid5s5nn+uj/0x5dwWV5TNpFYz9OMWXvYf0znWyIxekSzRlZH/bQWHzfMlqA96EsvqAsKqUraHpiZQ=
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)(376002)(346002)(396003)(136003)(39860400002)(46966005)(54906003)(53546011)(6512007)(6862004)(5660300002)(336012)(70206006)(83380400001)(8676002)(47076004)(8936002)(316002)(26005)(82310400003)(450100002)(186003)(70586007)(6506007)(2616005)(6486002)(2906002)(36756003)(81166007)(356005)(82740400003)(33656002)(478600001)(4326008)(86362001)(966005); DIR:OUT; SFP:1101;
X-OriginatorOrg: arm.com
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 04 Sep 2020 15:51:15.1491 (UTC)
X-MS-Exchange-CrossTenant-Network-Message-Id: ed2cf1c8-0522-4b6e-152f-08d850ea5af6
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: DB5EUR03FT055.eop-EUR03.prod.protection.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Anonymous
X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB7PR08MB3802
Archived-At: <https://mailarchive.ietf.org/arch/msg/cbor/Ar_Ai4lucqxoQ-IOFIiFaAEtej0>
Subject: Re: [Cbor] Ordering of items in the prefix table
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: Fri, 04 Sep 2020 15:51:22 -0000

I’ve been thinking about how dictionaries and nested tables interact. I have been wondering about the possibility of using references that overflow the nearest table to handle nesting. For the nesting-only case, this is straight-forward: when the decoder encounters a reference, it first checks to see if the reference fits in the nearest table. If it overflows the number of elements in that table, the size of the table is subtracted from the reference, then the decoder checks the next-nearest table.

This allows the decoder to treat the nested tables as a stack, pushing the most-recently encountered table onto the stack each time it finds one. Each time the traversal of a packed structure ends, it pops the table off of the stack.

This has the advantage a packed object can be included as-is in a larger packed object. A packed object can either be aware of the higher-level object or oblivious.

I’m assuming that a dictionary reference will live in its own tag, with an identifier:

7([rump, id])

That would make it easy to use the technique above with dictionaries. If the identifier is anything other than an array, we don’t need a separate tag, which is pretty nice.

Brendan

> On 28 Aug 2020, at 23:14, Carsten Bormann <cabo@tzi.org> wrote:
>
> On 2020-08-29, at 00:06, Michael Richardson <mcr+ietf@sandelman.ca> wrote:
>>
>>> This is easy with just one kind of table entry, but gets harder when
>>> prefixes can reference shared items which can reference other prefixes
>>> and so on.
>>
>> I think that things in the static dictionary(ies) can not reference things in
>> the shared (dynamic) dictionary.  I am grumpy about the terminology now, btw.
>> "shared" is a bit ambiguous now.
>
> The draft currently does not have dictionaries (which would be a term for external dictionaries to be added to the information in the internal tables).
>
> It has two tables:
>
> — shared items
> — prefix items
>
> The internal referencing works by giving the index of the item in the table; these are the “numbers” I have been talking about.  The ordering of items in the number space is relevant for the achievable compactness.  Both shared items and prefix items can contain references to shared items and prefix items.
>
> None of this is static or dynamic; adding external dictionaries might give these terms a useful meaning (that I haven’t picked up yet).
>
> Grüße, Carsten
>
> _______________________________________________
> 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.