Subject: Re: [apps-discuss] Concise Binary Object Representation (CBOR) -- new version -01

From: "Manger, James H" <[email-masked]>
Date: Tue, 4 Jun 2013 01:21:17 +1000

Nico makes an important point about an ignorable tag being unsuitable as a chunking indicator.
 
Consider an object with a 'to' field that can hold 1 or more names -- either as an array of strings, or (if there is only 1 name) as a string without the array wrapped.
Example 1: { "to":["alice", "bob"] }
Example 2: { "to":"joanne" }
Consider the following CBOR encoding:

 A1                   -- map
    62 746F           -- "to"
    C5                -- tag=chunked
       82             -- array
          62 6A6F     -- "jo"
          64 616E6E65 -- "anne"

If the tag C5 is ignored, an app will decode a "to" field with 2 names "jo" and "anne". If the tag C5 is recognized, an app will decode a "to" field with 1 name "joanne" that just happened to be sent in 2 chunks. There must be no possibility of an app confusing these.

We could state tag C5 MUST NOT be ignored. Though using the same tagging mechanism for other things that are truly optional is a bit messy.

Perhaps a cleaner solution is to use the indefinite flag (additional info 31) with other major types.
A CBOR item consists of:
* a major type: POSITIVE | NEGATIVE | BYTES | STRING | ARRAY | MAP | TAGGED | SIMPLE_OR_FLOAT;
* a mode: 0BYTES | 1BYTE | 2BYTES | 4BYTES | 8BYTES | RESERVED28 | RESERVED29 | RESERVED30 |
INDEFINITE
* additional info
* optional content

When mode is INDEFINITE (and major type isn't SIMPLE_OR_FLOAT), the content consists of all following CBOR items up to the special BREAK item (which is SIMPLE_OR_FLOAT/INDEFINITE).

ARRAY/INDEFINITE and MAP/INDEFINITE are as defined in draft 01.
BYTES/INDEFINITE is a byte array in chunks. The following items MUST be BYTES/not-INDEFINITE.
STRING/INDEFINITE is a string in chunks. The following items MUST be STRING/not-INDEFINITE.

I would probably go further and say POSITIVE/INDEFINITE conveys a bignum. There MUST be exactly 1 following item that is BYTES/not-INDEFINITE. Similarly NEGATIVE/INDEFINITE conveys a negative bignum.

I don't have any semantics to assign to TAGGED/INDEFINITE, but at least it can be decoded in the same way as the other */INDEFINITE items.

P.S. On chunked bignums
> >> Bignums can get very big.  That's... their point :)
> >
> > This is just proof by lack of imagination, but I can't imagine
> serializing a bignum the size of which you don't know by the time you
> start serializing it.
> 
> Imagine JSON had bignums (doesn't, but imagine).

JavaScript might not, but JSON actually does have indefinite length bignums. A JSON number can have any number of decimal digits.
However, I am with Carten here. Don’t allow chunking for bignums, it is a complication that we will never need.

--
James Manger

> > Looking at the other tags that accept strings, the 30+ tags probably
> all want to accept chunking.
> > Of course, we could redefine them to just accept arrays with chunking
> semantics, saving a byte.
> > (21 to 23 can't be redefined that way unless we lose the "all the
> > things in this map/array are base64url" semantics.)
> 
> No, really, chunking is just indefinite-length encoding for string-like
> values.  We need it for the same reasons that we need indefinite-length
> encoding for arrays and objects.
> 
> If you disagree, then please explain the distinction between the two
> kinds of values (strings on one side, arrays/objects on the other).
> 
> > With respect to the first class thing:  Nothing stops us from
> proclaiming 0xc5 "first class".
> 
> You made it "truly optional".  (Not OPTIONAL, but proper use of
> RFC2119 words is a separate nit; I assume you meant OPTIONAL.)
> 
> > Symmetry always is appealing.
> > To add more apparent symmetry, we can always change it to 0xdf :-)
> 
> I don't care about aesthetics here.  I care about having indefinite-
> length encodings for *all* values that lack a bounded encoded size.
> That's a form of symmetry, but higher up in the stack.
> I don't mind chunking being expressed with a tag, as long as it's
> REQUIRED and as long as it's clear what other tags it can be mixed
> with.
> 
> (The fact that chunking was made a tag made me nervous because it made
> it seem like an after-thought, and I'm now convinced that's just what
> it was.  You misunderstood the point of chunking, it's being just
> another way of saying "indefinite-length without escaping".  I can see
> why you thought that my complaint as about lack of symmetry in the
> details of encoding, but it wasn't.)
> 
> Nico

---

From: Nico Williams <[email-masked]>
Date: Mon, 3 Jun 2013 15:49:20 -0500

> Consider an object with a 'to' field that can hold 1 or more names -- either as an array of strings, or (if there is only 1 name) as a string without the array wrapped.

I think the principle is sufficient, but what a great example!

> If the tag C5 is ignored, an app will decode a "to" field with 2 names "jo" and "anne". If the tag C5 is recognized, an app will decode a "to" field with 1 name "joanne" that just happened to be se…

Right.  I think it's fine to drop some unsupported tags on decoding
like the tag that says some value is a date, because the consumer has
no way to express that.  But all consumers can be expected to be able
to express strings and arrays, so that excuse wouldn't work for
strings.

> We could state tag C5 MUST NOT be ignored. Though using the same tagging mechanism for other things that are truly optional is a bit messy.

I would live with that.  I would prefer that the indefinite-length
encoding choice were encoded in the same place as definitely length
encoding.  It seems cleaner that way.  But this is a bit subjective.
What's objective is the need for indefinite length encoding at least
for all types that JSON does the same for.

> Perhaps a cleaner solution is to use the indefinite flag (additional info 31) with other major types.

Or use some of the currently unallocated values from type 7's
supplementary bits.

> JavaScript might not, but JSON actually does have indefinite length bignums. A JSON number can have any number of decimal digits.

Yeah, but it is constrained to IEEE 754 64-bit floating point values, no?

> However, I am with Carten here. Don’t allow chunking for bignums, it is a complication that we will never need.

But in CBOR bignums devolve into byte strings, so if chunking (really,
escape-less indefinite-length encoding of strings) is in the core, and
required, then there's no need to think about whether chunked bignums
are allowed: it falls out that they are, and at no extra
implementation cost.  Even if it were otherwise I think I'd still
stand on the principle that all unbounded-size values must have an
indefinite-length encoding, though I concede that the "chunking
bignums, meh" sentiment does come up.  But if "chunked bignums" falls
out of having chunked byte strings, well, hey, why complain?

Nico
--

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 3 Jun 2013 17:05:50 -0400

I can't see any case where chunked bignums was a requirement and even if
there was such a case it would be easy enough to convert them to binary
blobs.

This is what is done in XML Signature today, there is a number type but the
spec actually uses Base64 encoding.

An easy way to avoid this being an issue would be to limit the length field
of a bignum to 16 bits. That way you have a guarantee that an intermediate
processor with a fixed size buffer can always transcode to JSON. 64Kb is a
pretty reasonable size to expect applications would support.

---

From: Nico Williams <[email-masked]>
Date: Mon, 3 Jun 2013 16:15:13 -0500

> there was such a case it would be easy enough to convert them to binary

Who's to say that some mathematician doesn't need to encode truly
gargantuan (from our puny perspective) numbers.  Still, I too feel
unenthused about chunked bignums.

What interests me is that if bignums are byte strings (in CBOR as
proposed they are) and there's a chunked byte string encoding, then
chunked bignums are supported and there's no need to think about it or
write a line of extra code to make that feasible.  (If a codec has a
native bignum type that would require conversion to byte string first
then it might be difficult to stream bignums without having to have
arbitrarily large buffers, but we can't cater to every possible native
bignum representation.)

> pretty reasonable size to expect applications would support.

I would feel more comfortable eliding the whole problem by saying that
since bignums are encoded as byte strings they can be chunked like any
other byte string.  Since the chunking happens one layer lower, it
just works and who cares.  16-bit bignums will definitely feel small
for math apps.

Nico
--