Subject: [Cbor] 7049bis: Diagnostic notation gaps

From: Carsten Bormann <[email-masked]>
Date: Fri, 11 Sep 2020 22:46:10 +0200

Over at https://github.com/cbor-wg/CBORbis/issues/204, we have had an interesting discussion about closing some gaps in diagnostic notation coverage (there also is a proposal in https://github.com/cbor-wg/CBORbis/pull/205 which I’m not sure how to handle).

Basically, #204 stipulates that there should be diagnostic notation for all well-formed encoded CBOR data items, which makes a lot of sense to me.  
It then identifies two gaps:

* (_ ) is ambiguous whether it refers to 0x5fff (an indefinite length byte string with no chunks) or 0x7fff (an indefinite length text string with no chunks).  The proposal in #205 is to disambiguate this by adding characters, (_b ) vs. (_t ).

It occurred to me that a better way to represent these two encoded CBOR data items would be to use ‘’_ and “”_ (please excuse the smart quotes).  This is already allowed by the text in RFC 7049; we would just need to point it out by adding a sentence to the last paragraph of § 8.1.  Note that in RFC 7049 these notations are in principle ambiguous, i.e. ‘’_ could be a (_ ) (0x5fff) or (_ ‘’) or (_ ‘’ ‘’) and so on; we would probably just clarify that these are to be used for (_ ) only as the other ones already have good diagnostic notation.

* There is only one NaN in diagnostic notation, but there are many NaN values in IEEE 754.  (This is a bit like JavaScript, where the core language only exposes one NaN value, even if extensions such as array buffers give the programmer full access to all of them.)  #205 suggests a notation:

> The IEEE 754 representation of NaN carries a "payload" of up to 54 bits,
> not all of which may be zero, so we allow an encoding indicator to specify
> the exact hex representation. Thus the standard half-precision NaN may be
> represented as `NaN`, `NaN_1`, or `NaN_1_x7E00`, while a single-precision
> NaN with an all-ones payload is represented as `NaN_2_x7FFFFFFF`. Items
> like `NaN_1_x0000` or `NaN_1_x7C00` do not encode NaN in the hex
> representation and so are not valid diagnostic notation.

(The payload here is the sign bit and the 11/24/53 significand [sic!] bits; in the binaryxx formats there is an exponent intervening of 5/8/11 bits which must be all ones, and the significand may not be all zeroes — those are the values for the two infinities, so only ~ 53.9999999999999998398 bits are actually available.)

I think this is ugly as hell, but it also is the best proposal so far.

My questions to the WG are:

1. Are we ready to go for ‘’_ and “”_, with the clarification to be added?

2. Do we believe that this is the right way to handle NaN payloads?
   Should we add this to 7049bis (which would be new functionality) or should we do this in a separate document?
   (We did this for other diagnostic notation extensions, which are listed in RFC 8610.)

Note that diagnostic notation is qualified as “not for interchange”, but its use for testing in tools and for communication in specification documents makes it rather desirable to nail it down at a good level of specificity.

Grüße, Carsten

---

From: Thiago Macieira <[email-masked]>
Date: Fri, 11 Sep 2020 14:30:24 -0700

On Friday, 11 September 2020 13:46:10 PDT Carsten Bormann wrote:
> * (_ ) is ambiguous whether it refers to 0x5fff (an indefinite length byte
> string with no chunks) or 0x7fff (an indefinite length text string with no
> chunks).  The proposal in #205 is to disambiguate this by adding
> characters, (_b ) vs. (_t ).
> 
> It occurred to me that a better way to represent these two encoded CBOR data
> items would be to use ‘’_ and “”_ (please excuse the smart quotes).  This
> is already allowed by the text in RFC 7049; we would just need to point it
> out by adding a sentence to the last paragraph of § 8.1.  Note that in RFC
> 7049 these notations are in principle ambiguous, i.e. ‘’_ could be a (_ )
> (0x5fff) or (_ ‘’) or (_ ‘’ ‘’) and so on; we would probably just clarify
> that these are to be used for (_ ) only as the other ones already have good
> diagnostic notation.

That would mean needing to keep a state whether the payload was empty or not 
and backtrack. A diagnostic printer currently can see the 0x5f or 0x7f and 
print "(_ ", then continue on. In order to print ""_ for 0x7fff, it needs to 
forego printing the parenthesis opening.

The simplest solution is to add the "b" or "t" unconditionally.

> (The payload here is the sign bit and the 11/24/53 significand [sic!] bits;
> in the binaryxx formats there is an exponent intervening of 5/8/11 bits
> which must be all ones, and the significand may not be all zeroes — those
> are the values for the two infinities, so only ~ 53.9999999999999998398
> bits are actually available.)
> 

It would be far easier to dump the binary representation of the entire 
floating point number, including the exponent bits. If this format were 
allowed, a diagnostic printer with no support for stringifying floating point 
numbers could use it for other values too.

Second option would be to use it like gdb prints:

	-nan(0x20000)

The type information can be encoded as either "nanf" (float) and "nanf16" (for 
_Float16).

If parentheses are not a good idea, then a third option is to print only the 
significand bits, dropping the "0x" too. It's clearly hexadecimal, we don't 
need the "x". In that case, we'd use the _ modification to indicate encoding 
length, as "-nan_001_1" for a negative 16-bit signalling NaN.

Either way, the document should advise what to do when it comes to signalling 
/ quiet NaNs. The CBOR spec recommends that only the IEEE-recommended non-
signalling form be used

"If NaN is an allowed value, it must always be represented as 0xf97e00."

The table in Appendix A also lists 0xfa7fc00000 and 0xfb7ff8000000000000, 
which match the IEEE recommendations for QNaN. But the Wikipedia page warns 
that some (older?) machines invert it and encode signalling NaN with the 
topmost mantissa bit set.

I would recommend that it print "nan" only if it's one of those three. And if 
it's distinguishing the payload length, "nan" is only for the double-precision 
case, the others requiring "nanf" or "nanf16" (if using the variant with 
parentheses), or for the 16-bit with "nan_2" and "nan_3" for the single- and 
double-precision ones respectively if not using parentheses.

-- 
Thiago Macieira - thiago.macieira (AT) intel.com
  Software Architect - Intel DPG Cloud Engineering

---

From: Thiago Macieira <[email-masked]>
Date: Fri, 11 Sep 2020 14:47:14 -0700

On Friday, 11 September 2020 14:30:24 PDT Thiago Macieira wrote:
> allowed, a diagnostic printer with no support for stringifying floating
> point numbers could use it for other values too.

By the way, should we explicitly allow hexadecimal floating point notation?

Appendix A has:

   | 3.4028234663852886e+38       | 0xfa7f7fffff                       |

This would also allow printing 0xf.fffffp+124 or 0x1.fffffep+127. The first 
form is what glibc's printf %a formatter prints, the second is the far easier 
one to produce without a floating-point formatter, by just decoding 0x7f7fffff 
as sign = 0, unbiased exp = 127 , significand = 0xffffff.
-- 
Thiago Macieira - thiago.macieira (AT) intel.com
  Software Architect - Intel DPG Cloud Engineering

---

From: Carsten Bormann <[email-masked]>
Date: Sat, 12 Sep 2020 00:09:23 +0200

> By the way, should we explicitly allow hexadecimal floating point notation?

Yes:

https://tools.ietf.org/html/rfc8610#appendix-G.5

Grüße, Carsten

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 16 Sep 2020 13:32:08 +0200

Hi Thiago,

Let me try to recap the two proposals for 0x5fff/0x7fff:

* Add b/t.  The minimum change would be to only allow this for empty indefinite length strings (no chunks).  In which case there still would need to be some logic to only emit b/t when the indefinite length string closes right away.  If we don’t do the minimum change, we would have interop issues with all implementations that don’t know about this.

* Use ‘’_/“”_.  This is indeed the minimum change, because it is no change from RFC 7049, just pointing out that this stands for 0x5fff and 0x7fff, respectively (well, there is a small change in that this is clarified to stand for no chunks, so you would need to say (_ ‘') etc if you have empty chunks, but that is already natural).  A generator of diagnostic notation would indeed need some look-ahead (one byte) to do this on the fly.  We don’t know how many consumers already decode ‘’_/“”_, so it is hard to say what interop issues we’d have, but the alternative (_ ) cannot be decoded unambiguously anyway.

I have a preference for not adding mechanism where it is not needed (even though this requires some code in the implementation — but that is true for both cases).

Let’s discuss this some more today at the CBOR interim meeting.

Grüße, Carsten

> On 2020-09-11, at 23:30, Thiago Macieira <[email-masked]> wrote:
> 
> _______________________________________________
> CBOR mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cbor

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 16 Sep 2020 14:08:03 +0200

Obviously, we need to add something to enable diagnostic notation to represent NaN payloads.

First of all, I wouldn’t mind doing this in a separate document, so we don’t tie getting experience with such a notation into the “real soon now” schedule for 7049bis.

Discussing the technical merits of the various proposals:

We should make sure that the parsing doesn’t become complicated; that was one reason why having the “x” in there might be helpful.

Also, I would like the values that do not carry a _ to be independent of length, so “nan” would continue to stand for 0x7e00, 0x7f800000, etc.
(Note that there are some people that like those to stand for 0x7fff/0x7fffffff — one reason is that the negative NaN becomes 0xffffffff, which is also the result of some SIMD operations.)

I like the approach of enabling the dumping/loading of floating point values without understanding floating point at all.  Hex floats (part of EDN in RFC 8610) go a long way, but specifically do not address NaNs.  If we use something that looks like a number for that (0x…), we need to require length indicators (_1 _2 _3).  Maybe dumping the whole item in hex, including the head (f9/fa/fb), is the most versatile extension of DN/EDN that we can make.  If we go this way, we probably should make up a somewhat jarring syntax so this becomes readily visible and is visually *very* distinct from hexadecimal CBOR-in-a-byte-string (h’f97c00’).

Grüße, Carsten

---

From: Thiago Macieira <[email-masked]>
Date: Wed, 16 Sep 2020 08:20:07 -0700

On Wednesday, 16 September 2020 04:32:08 PDT Carsten Bormann wrote:
> * Add b/t.  The minimum change would be to only allow this for empty
> indefinite length strings (no chunks).  In which case there still would
> need to be some logic to only emit b/t when the indefinite length string
> closes right away.  If we don’t do the minimum change, we would have
> interop issues with all implementations that don’t know about this.

Indeed. The simplest for diagnostic dumpers would be to always allow "b" and 
"t" at that point, since the type has been decoded.

> * Use ‘’_/“”_.  This is indeed the minimum change, because it is no change
> from RFC 7049, just pointing out that this stands for 0x5fff and 0x7fff,
> respectively (well, there is a small change in that this is clarified to
> stand for no chunks, so you would need to say (_ ‘') etc if you have empty
> chunks, but that is already natural).  A generator of diagnostic notation
> would indeed need some look-ahead (one byte) to do this on the fly.  We
> don’t know how many consumers already decode ‘’_/“”_, so it is hard to say
> what interop issues we’d have, but the alternative (_ ) cannot be decoded
> unambiguously anyway.

Hmm... that's also a possibility, since this is currently an unused sequence.

$ printf '\x84\x58\0\x59\0\0\x5a\0\0\0\0\x5b\0\0\0\0\0\0\0\0' | ./cbordump -i
[
    h''_0,
    h''_1,
    h''_2,
    h''_3
]

Looking at my own code at https://github.com/qt/qtbase/blob/dev/examples/
corelib/serialization/cbordump/main.cpp#L294-L327, the complexity is about the 
same either way. There's already some state being kept across chunks work due 
to the comma. It wouldn't be too difficult to realise that the length wasn't 
known and nothing got printed.

> I have a preference for not adding mechanism where it is not needed (even
> though this requires some code in the implementation — but that is true for
> both cases).
>

---

From: Thiago Macieira <[email-masked]>
Date: Wed, 16 Sep 2020 09:05:52 -0700

On Wednesday, 16 September 2020 05:08:03 PDT Carsten Bormann wrote:
> We should make sure that the parsing doesn’t become complicated; that was
> one reason why having the “x” in there might be helpful.
> 
> Also, I would like the values that do not carry a _ to be independent of
> length, so “nan” would continue to stand for 0x7e00, 0x7f800000, etc. (Note
> that there are some people that like those to stand for 0x7fff/0x7fffffff —
> one reason is that the negative NaN becomes 0xffffffff, which is also the
> result of some SIMD operations.)

Clarification, do you mean that "nan" stands for all three possibilities? Or 
that it's one of them, the others being represented by nan_2 and nan_3? The 
same answer would apply for "inf", I presume.

As for the all-bits-set... I would prefer not to. The current 7049 says that 
the preferred forms are 7e00, 7fc00000, 7ff8000000000000, which match the 
quiet NaN that CPUs like x86 generate when they need to create a NaN out of 
non-NaN parameters. The other way around is important and is detailed on the 
Intel manual: the SIMD all-bits-set value has the NaN's quiet bit set.

> I like the approach of enabling the dumping/loading of floating point values
> without understanding floating point at all.  Hex floats (part of EDN in
> RFC 8610) go a long way, but specifically do not address NaNs.  If we use
> something that looks like a number for that (0x…), we need to require
> length indicators (_1 _2 _3).  Maybe dumping the whole item in hex,
> including the head (f9/fa/fb), is the most versatile extension of DN/EDN
> that we can make.  If we go this way, we probably should make up a somewhat
> jarring syntax so this becomes readily visible and is visually *very*
> distinct from hexadecimal CBOR-in-a-byte-string (h’f97c00’).

We can just use the 'f' prefix instead of 'h', unless you mean that that is 
not distinct enough. So, is f'7eff'_1 a sufficient output?

Personally, I'd prefer never to generate that. Printing as hexfloat isn't too 
difficult, so whenever possible I'd like to have my own code do that. For this 
reason, I'd like an alternative for NaN that has the letters "nan" somewhere 
in them, so I can see from the dump output that it is a NaN.

Especially as it gets bigger. Is f'7ff8000000000000'_3 or f'7f800000'_2 a NaN, 
infinity or just a very large number? 

"binary32 has 24 bits in the fraction, but one is implicit, so that is 23 bits 
dedicated to the mantissa; that leaves 32 - 23 = 9 bits for the sign and 
exponent; 9 bits need two hexadecimal digits plus one bit, so that "8" in 
"7f8" is still part of the exponent, which means the mantissa is zero, which 
means this number is positive infinity. Gah, just kill me now!"

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 16 Sep 2020 18:17:23 +0200

> On 2020-09-16, at 18:05, Thiago Macieira <[email-masked]> wrote:
> 
> Clarification, do you mean that "nan" stands for all three possibilities?

Yes, like 1.0 does. (With f93c00 as the preferred encoding of 1.0.)

> Or 

It’s actually Infinity, -Infinity, and NaN.

> Intel manual: the SIMD all-bits-set value has the NaN's quiet bit set.

Some diagnostic notation writers will put out 0xffffffff as NaN (as defined in RFC 7049).  Some may make use of new notation we come up with.

> not distinct enough. So, is f'7eff'_1 a sufficient output?

Well, that is rather close.  Foo’baaa’ is for byte strings, so this would be a clear deviation.

> in them, so I can see from the dump output that it is a NaN.

OK, sticking with your proposal:  NaN’7e00’_1 (or maybe NaN’7e00’ as we don’t really have leading zero bytes in a NaN?)
This of course means NaN’7c00’ (or NaN’3c00’) would be invalid, as these are not NaNs.

Grüße, Carsten

---

From: Thiago Macieira <[email-masked]>
Date: Wed, 16 Sep 2020 09:58:37 -0700

On Wednesday, 16 September 2020 09:17:23 PDT Carsten Bormann wrote:
> > As for the all-bits-set... I would prefer not to. The current 7049 says
> > that the preferred forms are 7e00, 7fc00000, 7ff8000000000000, which
> > match the quiet NaN that CPUs like x86 generate when they need to create
> > a NaN out of non-NaN parameters. The other way around is important and is
> > detailed on the Intel manual: the SIMD all-bits-set value has the NaN's
> > quiet bit set.
> Some diagnostic notation writers will put out 0xffffffff as NaN (as defined
> in RFC 7049).  Some may make use of new notation we come up with.

It is *a* NaN, but not *the* NaN. That value should produce the letters "NaN" 
somewhere, but it will need more details to disambiguate.

> > Personally, I'd prefer never to generate that. Printing as hexfloat isn't
> > too difficult, so whenever possible I'd like to have my own code do that.
> > For this reason, I'd like an alternative for NaN that has the letters
> > "nan" somewhere in them, so I can see from the dump output that it is a
> > NaN.
> 
> OK, sticking with your proposal:  NaN’7e00’_1 (or maybe NaN’7e00’ as we
> don’t really have leading zero bytes in a NaN?) This of course means
> NaN’7c00’ (or NaN’3c00’) would be invalid, as these are not NaNs.

Indeed. I think that's acceptable as it allows code to detect that the FP 
number is a NaN and then simply dump the entire thing, without having to 
understand which bits are mantissa and which ones aren't.

GCC's intrinsic __builtin_nanf16("0x1") is NaN'7e01', but fortunately it also 
generates the same thing for __builtin_nanf16("0x7e01"). It just masks off the 
high bits, including the sign bit, so to generate NaN'fe00', you'd write 
-_builtin_nanf16("").

To confirm I understand you, are these sequences identical to each other (in 
the same line)?

  NaN_1	NaN'7e00'		NaN
  NaN_2	NaN'7fc00000'
  NaN_3	NaN'7ff8000000000000'

(the bit patterns are the QNaN, unless I made a mistake; I'm not trying to 
trick you)

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 16 Sep 2020 23:37:55 +0200

>  NaN_3	NaN'7ff8000000000000'

That was my intention, except that NaN is unspecific about encoding length just as 1.0 is, so it should be on all three lines (but the first one is the preferred encoding).

(I still have to check the syntax whether NaN’…’ bites us anywhere, but I think it shouldn’t.)

> (the bit patterns are the QNaN, unless I made a mistake; I'm not trying to 

RFC 7049 is trying to help you :-)

$ grep NaN rfc7049.txt | grep 0x
   | NaN                          | 0xf97e00                           |
   | NaN                          | 0xfa7fc00000                       |
   | NaN                          | 0xfb7ff8000000000000               |
$

Grüße, Carsten

---

From: Carsten Bormann <[email-masked]>
Date: Tue, 22 Sep 2020 23:45:49 +0200

>   (We did this for other diagnostic notation extensions, which are listed in RFC 8610.)

I think we now have a clear way forward for diagnostic notation for both 5fff/7fff and NaN payloads.

The former ostensibly has not really been a gap in RFC 7049, so we could address it in a clarification in 7049bis.

The latter is a new invention and so cannot really part of 7049bis, which is slated for Internet Standard and needs to meet the spirit of RFC 6410, which says:

   Minor revisions and the removal of unused
   features are expected, but a significant revision may require that
   the specification accumulate more experience at Proposed Standard
   before progressing.

Extending diagnostic notation is not a significant revision in that it will shatter the CBOR universe, but it is still new untested code that really should be in a separate document.

I would therefore like to close #204 and #205 now, and (if we want to treat 5fff/7fff as a clarification) add a small pull request for just that.

Grüße, Carsten