Subject: Re: [Cbor] draft-jroatch-cbor-tags-04

From: Johnathan Roatch <[email-masked]>
Date: Wed, 03 Aug 2016 12:32:03 -0400

On Thu, 2016-07-28 at 18:09 -0700, Sean Leonard wrote:
> Section 2. Typed Arrays
> 
> Okay; makes sense. However, the mismatch between [u/s]int8 and
> binary16 
> is jarring. It would seem a lot better if 
> uint16/sint16/binary16..uint128/sint128/binary128.

When I initially made up the scheme, my primary goal was to pack in any
possible gaps. I agree now that byte sizes should definitely be
aligned, especially to include 128-bit integers.

> In contrast, I don't see a lot of value to tagging an array as
> uint8...that would be called a plain old "byte string" by any
> definition of the term.

Good insight here. I confused myself thinking that a JavaScript
ArrayBuffer could been used without a uint8 view. The uint8 tag can
definitely be dropped to make room for byte size alignment.
Implementations should then use un-tagged byte strings for uint8
arrays.

> For the case of uint8 and sint8, I propose that you allocate four
> tags in approximately 0b001111_c_s, where c = clamped, and s =
> signed. 

If the uint8 is gone then all we have left here is sint8. clamped
arithmetic isn't as critical to fit into some bit pattern as it's
really just a hint on how to process numbers and not a number format on
it's own. Now that I think of it, clamped arithmetic can actually be
it's own tag that can apply to any integer or integer array.

> If you want parity with the bit positions in the other tags, I would
> propose rearranging the 0b010_f_s_e_ll to: 0b010_ll_f_e_s

I put float and signed together to form the collective bit field of
number type, and those bits were made the most significant so that
there would be less gaps in the list of tags. We have 3 types of
numbers in a field that can hold 4. Maybe a fourth type of number
should fill in those gaps.

Are the IEEE 754-2008 decimal formats used enough to include them?

After playing around with possible arrangements a bit this would be
what I would do: 0b01_lll_f_s_e.
"lll" is the used as "2**(lll)" for calculating the number of bytes.
All tags of a single byte size, except sint8, are unreserved. This will
make is simple to compute, as all it would take on most platforms is a
bit-mask and a couple shifts. the unreserved space will also be a good
place to put related tags such as Homogeneous and Multi-dimensional
Arrays.
"f_s" is the number format: [uintN, sintN, IEEE 754 binaryN, IEEE
754 decimalN].
"e" is big or little endianness.

In this formulation, uint8 is no tag, uint16-LE is tag 0x49, IEEE 754
binary32-LE is tag 0x55, uint128-LE is 0x61, and I guess sint8 can be
tag 0x42.

> I would also like to suggest using tags in the 2-byte space, such as 
> 0x0220-0x0237 (or 0x021C - 0x0237). 

Since there's already implementations that follow the old drafts, going
to the 2 byte tag space might be necessary for backwards compatibility
of those implementations.

If we are going to reuse the original range, now is the time to have a
breaking change.

> I suppose that you have thought of this already. I am less concerned
> about low-byte "pollution"; 

About "low-byte pollution", I've heard criticism about how endianness
takes up too many tags. While I thought about separating out endianness
to it's own tag, it's doesn't make much sense outside of the context of
typed arrays.

If we include IEEE 754-2008 decimal while fixing up the byte size
aliment as I wrote above, the total amount of tags will increase from
24 to 32. Forcing everything to be little-endian will reduce that
amount to 16. It really depends on how important having big endianness
is.

> it has more to do with the need for expansion of typed arrays in the
> future. If you want to add binary256, int256, etc.,

For now, I think we should limit ourselves to 128 bit arrays.

> Section 7. Security Considerations
> 
> ...
> 
> I consider an irregular-length array to be a coding error; that is
> with my security hat on.

Yes.

Would it be right to say that in the case of such a coding error, the
implementation should either terminate processing or treat the byte
string as if there were no TypeArray tag applied to it (as uint8)?

-- 
Johnathan Roatch <[email-masked]>
https://jroatch.nfshost.com/

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 4 Aug 2016 00:22:02 +0200

Hmm, I’m not sure I agree with either the criticism or the conclusions below.
As the draft stands, it is closely mirroring the typed array functionality that has been defined in several environments including JavaScript.  Why would we be chasing some form of symmetry instead of following what the users seem to need?

uint8/sint8 arrays are arrays of integers, which is different from untagged byte strings.  Hence the tags.
I’m not aware of a use case for IEEE 754 decimal at this point.  Sure, one can be constructed, but the objective is not to cover everything that has been invented under the sun, but what is actually needed.

In summary, I continue to believe that the draft is all good as it stands; nothing should be changed.

Grüße, Carsten

On 3 August 2016 at 18:57:07, Johnathan Roatch ([email-masked]) wrote:

Yes.

---

From: Sean Leonard <[email-masked]>
Date: Wed, 3 Aug 2016 16:29:20 -0700

Hello Johnathan,

Glad to see that my review was helpful. Additionally:

> aligned, especially to include 128-bit integers.

Great.

> Implementations should then use un-tagged byte strings for uint8

The issues here have to do with code complexity (branches versus 
jumping) and semantics. When handling JavaScript array buffers, is there 
a meaningful distinction between uint8 arrays and "byte strings", such 
that the semantic difference needs to be encoded on the wire?

> it's own tag that can apply to any integer or integer array.

Yes, it could. I have not formed an opinion yet of whether it should or 
should not be. There is a technique discussed in 
draft-bormann-cbor-tags-oid, to stack tags, so that you can have tag1 ( 
tag2 ( cbor ) ), which can have various semantics. In that case, a 
proposal is that the first tag applies uniformly to the keys in a map; 
the second tag (inner tag) (if present) applies uniformly to the values. 
But that is only proposed for certain binary identifiers, namely for 
OIDs and UUIDs.

When I wrote that proposal, I did not intend it to be general semantic 
advice. However it might be useful.

If you have a wider block of tags (i.e., in the two-byte tag range), you 
can use more bits.

> Are the IEEE 754-2008 decimal formats used enough to include them?

Clearly IEEE 754 decimal formats are important enough that a group of 
(very talented) academics and engineers got together to write a (very 
expensive) standard about it.

http://dec64.com/
http://dx.doi.org/10.1109/AICERA-ICMiCR.2013.6575957

floating point decimal appears to have applications in financial, 
astronomical, or scientific calculations. I would not be surprised if 
there are chemical applications as well.

These applications make sense. For finance (not accounting), such as 
financial engineering, preserving base 10 for derivatives etc. makes 
sense as well as very small fractions of currency units in orders of 
magnitude (i.e., 10^-x). For very large or very small physical 
calculations (distances between stars, molecular weights, mols, SI 
units), preserving base 10 is absolutely essential.

We don't see decimal formats much around IETF because the most 
math-intensive stuff tends to be about routing (which has to do with 
graph and set theory), latency/time calculations (which can be measured 
in fixed units, e.g., nanoseconds), and cryptography (where a single bit 
of rounding error is designed to be fatal). That does not mean they are 
not useful.

JavaScript Typed Arrays are mainly based on binary (base 2) floating 
point because a big application is for web graphics, like games, 
animation, and video and whatnot. Also it doesn't hurt that JavaScript 
has binary floating point built-in. But CBOR is about far more than the 
web and far more than graphics.

I say, put a call or email in to one of the IEEE 754 people.

Overall, I think it's worth an extra bit in the major type 6 (tag) space 
(as you propose below). It would be too difficult to add floating point 
decimal to add it to the major type 7 (simple) space, but I think we 
kind of all know that.

Maybe it would be good to have a tag to tag a single type 7 (simple) 
floating-point number as decimal instead of binary. A bit out of scope, 
though.

> If we are going to reuse the original range, now is the time to have a

(Note: when I wrote 2-byte space, I meant 2 bytes for the integer and 
one byte for the major type and additional information byte, hence 2+1=3 
bytes.)

> amount to 16. It really depends on how important having big endianness

Network byte order is big-endian. It would be a bit silly not to support it.

I'm seeing 32 * 2 = 64...

Overall, what is the length of the tagged binary arrays that we are 
talking about? I am thinking that the number of items in each array will 
significantly dwarf the difference between a 40-255 tag (two bytes) and 
a 256-65535 tag (three bytes, what I earlier called "2-byte space").

> string as if there were no TypeArray tag applied to it (as uint8)?

To me, "enforce" means fatal (fail processing) if not met.

A low-level, generic CBOR decoder would not enforce anything related to 
the tags.

Actually I would argue that a "secure" low-level, generic decoder would 
enforce the simple types (right now, there's not much to enforce...other 
than for types 25-27, 16, 32, and 64 arbitrary bits follow, and for 24, 
one byte follows), and would enforce uniqueness of keys in a map, pairs 
of keys/values in a map, and (importantly) UTF-8 conformance. It is not 
clear whether a "secure" low-level, generic decoder ought to enforce 
"smallest number of bytes per integer" (aka prohibit overlong 
encodings). For example, tag 0 can be encoded as C0 or D800; unsigned 
integer 0 can be encoded as 00, 1800, or even 1A00000000. RFC 7049 
doesn't say these are erroneous, so I guess they are okay. Actually RFC 
7049 Section 3.6 specifically discusses this. (Unicode says overlong 
encodings are bad, hence why a "secure" CBOR decoder needs to enforce it.)

I would expect that a generic CBOR decoder that is aware of a tag's 
semantics, would enforce the tag's semantics. More tags mean more code. 
Since a large block of tags is getting allocated, it would definitely 
save on decoder complexity if all the tags are in one contiguous block 
(hence arguing more for the 2-byte range 256-65535) and therefore a 
decoder could enforce length multiples based on a small handful of bits 
and a couple of shift ops. In that case you could allocate a couple of 
extra spare bits for future growth. Nobody is going to bat an eye at 
allocating 256 or even 512 or 1024 tags out of the 256-65535 range.

Such a tag-aware CBOR decoder needs to be aware of the overlong encoding 
issue, for any tag that is not in the 33-64 bit range.

Sean