Subject: Re: [Cbor] [COSE] [Rats] RAM requirements for COSE/CWT

From: Jeremy O'Donoghue <[email-masked]>
Date: Tue, 1 Mar 2022 09:41:14 +0000

Hi Carsten, Laurence,

On 01/03/2022, 05:40, "COSE" <[email-masked]> wrote:

WARNING: This email originated from outside of Qualcomm. Please be wary of any links or attachments, and do not enable macros.

On Feb 23, 2022, at 1:08 PM, Carsten Bormann <[email-masked]<mailto:[email-masked]>> wrote:

Hi Laurence,

I know in reality most decoders will handle non-preferred serialization, but I don’t see anything in section 5.2 that says that they must. (non-preferred is still well formed).

What part of the first sentence of section 5.2:

A generic CBOR decoder can decode all well-formed encoded CBOR data items and present the data items to an application.

...could we have phrased better?

Well, um, maybe.  :-)

It’s a small sentence with potentially big implications.

If your generic decoder is like the pseudo code the implications aren’t big, but for decoders like QCBOR that do a lot more work for you, the implications are large — deep combined nesting of interleaved definite length and indefinite lengths maps and arrays, huge indefinite length strings, multiple levels of tag nesting for a data item that is a map label, a nested set of maps that is used as a map label,…

I haven’t checked, but there might not be very many truly conformant generic decoders. QCBOR definitely isn’t, because it has limits like a max of 4GB for encoded input, max levels of map, array and tag nesting and such to be efficient with code size and memory.

[JOD] In strong agreement with Laurence here. I’ve written two CBOR codecs that I believe to be complete, and which try to do quite a lot of the work for the caller: one in Rust (WIP Open Source) and one in Haskell (unpublished).

Thanks to the magic of the Garbage collector, the Haskell decoder can offer an exceptionally ergonomic interface and breezes through most of the problem areas listed, up to the limit of the memory available to a process on the device (I tested it with an auto-generated 2GB token with pretty complex nesting). It is also very large and utterly unsuited to any embedded target I can think of – code plus dependencies plus runtime is about 4MB on my machine.

The Rust version is almost the opposite – it is designed for constrained embedded devices and necessarily has compile-time limits on the size of the input token, limits on nesting and many of the other limitations mentioned above. It’s also about 11kB of code on the same machine (running Rust no_std, so the runtime is almost non-existent – a panic handler and an entry point).

A truly conforming generic decoder is likely to have more in common with the Haskell implementation than the Rust one, but the applicability is necessarily entirely different. Constrained targets will require their CBOR implementations to make implementation decisions that constrain the acceptable input.

This does suggest to me that EAT profiles (and indeed any specification that uses CBOR) might be wise to indicate minimum capability in a decoder in some way. This is most simply expressed in terms of a token size that MUST be accepted, but in the real-world there might be further limitations on nesting depth and the like.

As an interesting aside, during experiments in code-generation from CDDL, one of the challenges is that the structure of the CDDL AST leads to generated code which potentially nests very deeply – I am still looking for ways to handle this efficiently.

That said, probably most decoders can handle non-preferred integers, the topic at hand, just fine because it is trivial.

[JOD] Indeed – non-preferred integers require literally no code in most cases. One thing I would really like to see, and haven’t found so far, is a reliable mechanism to determine the preferred encoding for floats. Currently my implementations require the caller to decide on the float encoding (float16, float32, float64) as I haven’t been able to find a reference that explains how to straightforwardly determine the most efficient *encoding* for a float without loss of precision.

Jeremy

Yes you are of course right that 5.2 that defines generic decoders says non-preferred serialization must be supported.

LL

---

From: Carsten Bormann <[email-masked]>
Date: Tue, 1 Mar 2022 11:16:13 +0100

On 1. Mar 2022, at 10:41, Jeremy O'Donoghue <[email-masked]> wrote:
> 
> One thing I would really like to see, and haven’t found so far, is a reliable mechanism to determine the preferred encoding for floats. Currently my implementations require the caller to decide on the float encoding (float16, float32, float64) as I haven’t been able to find a reference that explains how to straightforwardly determine the most efficient *encoding* for a float without loss of precision.

Ready for copying:

https://github.com/cabo/cbor-ruby/blob/master/ext/cbor/packer.h#L138

(Don’t be confused by the “msgpack” prefixes; this code was adapted from the msgpack implementation, and to enable updates from upstream, the renaming is done with a bunch of #defines in renamer.h.)

Note the magic lines

 float fv = v;
  if (fv == v) {     … encode as binary16 or binary32 instead of binary64

Which do all the work here.

Unfortunately C doesn’t have a portable way to say the same for binary16, so there is some more extensive code following.

Grüße, Carsten

---

From: Laurence Lundblade <[email-masked]>
Date: Tue, 1 Mar 2022 14:21:17 -0800

Got it. Made PR to remove half-precision exclusion <https://github.com/ietf-rats-wg/eat/pull/172> from location. Thanks for the discussion and foot notes!

Checked a few decoders and can see that half-precision decoding is often supported.

LL

> On Feb 23, 2022, at 1:08 PM, Carsten Bormann <[email-masked]> wrote:
> 
>>> 
>>> This discussion was more about lat/lon.  
>>> cti (label 7) is a byte string, so there is no such problem there.
>> 
>> Lat/long needs double precision float to be useful to beings the size of humans on a planet of earth's size. Half-precision has so little precision on a planet of earth's size that it is useless for location.
> 
> That is not what this is about.
> 
> Saying “You need 16 bits to express the unsigned integer weight of a street vehicle in kg” does not mean that I can’t encode the weight of my bike in 8 bits.
> What the current text in EAT says is equivalent to "you can’t ever use 8 bits because some vehicles need 16".  That is not smart.
> 
>> I mis-remembered “iat” as “cti”. Iat is a time stamp. A uint64 can represent everything needed for a time stamp, 1 second precision and +/- 500 million years. Float adds no value.
> 
> Right, but that is OK: It is a restriction at the data model level.  You are asking the application not to feed floats into the generic encoder.
> 
> (Note that we strengthened the little wall between integer and floating point for RFC 8949, after seeing that RFC 7049 was confusing people a lot.)
> 
>> 
>> So EAT
>> - disallows half-precision in location, but allows doubles to relieve a decoder from implementing half-precision
> 
> Bad.  Half-precision (binary16) is not a different type at the data model level, it is just an efficient way to represent certain numbers in your data model.
> Binary16 has a significand [sic] precision of 11 bits.  Binary32 has 24 bits.
> So if you feed random binary32 lat/lon (~ meter precision) to your generic encoder, every 8192th will be encoded in half-precision (*).
> 
> Since lat/lon values are probably approximately evenly distributed, that by itself is not a reason to implement half-precision.
> The fact that CBOR preferred encoding does employ half-precision is.
> Deviating from that by disallowing binary16 is expensive: You no longer can employ generic encoders.
> 
> Don’t do that.
> 
>> - disallows float for iat to relieve a decoder from implementing float, assuming it is not implementing location (many EAT implementations will not support location)
> 
> Good(**).  That selection of integer second timestamps is a part of your data model.  
> You can do that, and no generic encoder will suddenly turn your integer iat number into a float.
> (Again, with RFC 7049, it possibly could have, but we fixed that.)
> 
> Grüße, Carsten
> 
> (*) Note that a similar thing happens in JSON: numbers that happen to be whole numbers will be encoded without fractional parts (10.0 becomes 10).
> In certain decoder implementations, that makes them a different “type" than 10.0 or 1e1 or 0.1e2 etc., causing breakage.
> But the JSON data model only has numbers, not integers as a separate, incompatible type, so these decoders are broken with applications that simply expect numbers.
> (Find ISO 6093:1985 for some fascinating history in this space :-)
> 
> (**) ((I’m not making any representation on whether applications need to know with a precision of smaller than a second when your EAT was issued.  
> I really can’t imagine that, but that is proof by lack of imagination; I do assess that the cost of enabling that is higher than the benefits.  
> But that is true until someone has a convincing counterexample…  
> Consolation is that these people can introduce a float iat = “fiat” :-)))
>

---

From: Anders Rundgren <[email-masked]>
Date: Wed, 2 Mar 2022 05:45:31 +0100

> Checked a few decoders and can see that half-precision decoding is often supported.

Encoders can also provide full support (including subnormal values) for half-precision at the expense of 100-150 bytes of code:
https://github.com/cyberphone/D-CBOR/blob/main/lib/d-cbor-ieee754.c

Anders

> _______________________________________________
> RATS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/rats