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

Carsten Bormann <cabo@tzi.org> Fri, 28 August 2020 18:30 UTC

Return-Path: <cabo@tzi.org>
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 020D43A0869; Fri, 28 Aug 2020 11:30:30 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.897
X-Spam-Level:
X-Spam-Status: No, score=-1.897 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_MSPIKE_H4=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
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 2sgr2Cjt-76V; Fri, 28 Aug 2020 11:30:27 -0700 (PDT)
Received: from gabriel-vm-2.zfn.uni-bremen.de (gabriel-vm-2.zfn.uni-bremen.de [134.102.50.17]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id CD5A43A078C; Fri, 28 Aug 2020 11:30:24 -0700 (PDT)
Received: from client-0018.vpn.uni-bremen.de (client-0018.vpn.uni-bremen.de [134.102.107.18]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by gabriel-vm-2.zfn.uni-bremen.de (Postfix) with ESMTPSA id 4BdSnp6b14zyX7; Fri, 28 Aug 2020 20:30:22 +0200 (CEST)
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 13.4 \(3608.120.23.2.1\))
From: Carsten Bormann <cabo@tzi.org>
In-Reply-To: <29638.1598639086@localhost>
Date: Fri, 28 Aug 2020 20:30:22 +0200
Cc: Jim Schaad <ietf@augustcellars.com>, draft-bormann-cbor-packed@ietf.org, cbor@ietf.org
X-Mao-Original-Outgoing-Id: 620332222.440344-2f72313b827bdce7f9fd0ac2339e3acf
Content-Transfer-Encoding: quoted-printable
Message-Id: <B7320B50-BB7D-4E0C-BA11-E35B69F90867@tzi.org>
References: <008d01d67c48$d25c4440$7714ccc0$@augustcellars.com> <29638.1598639086@localhost>
To: Michael Richardson <mcr+ietf@sandelman.ca>
X-Mailer: Apple Mail (2.3608.120.23.2.1)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cbor/pX-kheBEJBZx4twZoBRxRlY-zZs>
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, 28 Aug 2020 18:30:36 -0000

On 2020-08-28, at 20:24, Michael Richardson <mcr+ietf@sandelman.ca> wrote:
> 
> 
> Jim Schaad <ietf@augustcellars.com> wrote:
>> I was just going through an expansion algorithm and I started to wonder if
>> we should have a requirement about order of items in the prefix table.
>> Specifically if an entry in the prefix table uses a prefix itself  (i.e.
>> entry 3 in the table is 6.2872("foo")), does that entry need to occur after
>> the entry it references?
> 
> I also asked that question.
> If we don't enforce that rule, then the decoder has to take care of dealing
> with loops.

Right.

> This means either having a maximum loop depth, or, using a mark to refuse to
> expand any specific dictionary item more than once.
> I would prefer that all references are forward references.

(Backward references?)

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.

Of course, the tables could be merged, but that loses exactly one bit per reference that can be derived from the prefix vs. shared reference.

One other thing to keep in mind is that not all places in the table are equal — the compressor will likely sort the entries by frequency of use.  Requiring infrequent entries to occupy all the good positions does not lead to very compact encoding.

Grüße, Carsten