Subject: [Cbor] Fwd: [netmod] CBOR YANG encoding of union & bits [draft-ietf-core-yang-cbor-12]

From: Carsten Bormann <[email-masked]>
Date: Wed, 6 May 2020 17:38:06 +0200

JFYI: Interesting discussion in core/netmod about potentially needing to represent sparse bit sets.
Anything we (cbor WG) can contribute to that?

Grüße, Carsten

> Begin forwarded message:
> 
> From: "Rob Wilton \(rwilton\)" <rwilton=[email-masked]>
> Subject: [netmod] CBOR YANG encoding of union & bits [draft-ietf-core-yang-cbor-12]
> Date: 2020-05-06 at 12:43:49 CEST
> To: "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
> Archived-At: <https://mailarchive.ietf.org/arch/msg/netmod/zaAtN5l8NuXUT1u3oj3qy9UG_m8>
> 
> Hi,
> 
> [Cross posting to Netmod for wider YANG expertise.]
> 
> I had a couple of questions on the CBOR YANG encoding of bits and unions (based on draft-ietf-core-yang-cbor-12).  Apologies if these have already been discussed/closed in the WGLC.
> 
> 1) Regarding the encoding of the bits datatype:
> [draft-ietf-core-yang-cbor-12, section 6.7]
> 
> The CBOR YANG encoding of the bits datatype is defined as a byte string encoding of a bitfield.  However, my concern here is that YANG bit positions are allowed to be up 2^32-1.
> 
> E.g. the following, pathologically bad, bits definition would seem to have a very inefficient encoding in CBOR:
> 
>   typedef alarm-state {
>     type bits {
>       bit unknown {
>         position 4000000000;
>       }
>       bit under-repair;
>       bit critical;
>       bit major;
>       bit minor;
>       bit warning;
>       bit indeterminate;
>     }
>   }
> 
> 
> How much should we be concerned about this pathological case?  Would it be reasonable for implementations to reject bitfields larger than a small set size (e.g. perhaps 256 bits)?
> 
> Or, if it is supported by the language then is it reasonable that implementation SHOULD support it?  In which case I think that we might need a second encoding of bits that supports this pathological case.  Perhaps an array of 'set' bit positions, or alternatively the union string encoding of bits could be used.
> 
> 
> 2) Regarding the encoding of unions:
> 
> I was questioning whether the special encoding of bits type within a union was required in CBOR [draft-ietf-core-yang-cbor-12, section 6.7].  Am I right to presume that this is to ensure that the CBOR encoding of unions is always at least as specific as XML?  If so, this seems like a reasonable design choice.  But that leads on to these general YANG questions:
> 
> Should the value encoding of a YANG union type behave the same way regardless of whether the encoding is XML/JSON/CBOR?  Or is it reasonable for there to be differences in the case of conflicting values?  Perhaps this is already answered by RFC 7951 that can behave differently from the XML encoding of unions.
> 
> Longer term, should YANG be looking for a discriminated-union type?  Or perhaps it would be sufficient for tooling to flag up potentially ambiguous union definitions, particularly those that may be encoding dependent.
> 
> 
> Regards,
> Rob
> 
> [As an individual contributor]
> 
> 
> 
> 
> 
> 
> 
> 
> _______________________________________________
> netmod mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/netmod

---

From: Kio Smallwood <[email-masked]>
Date: Wed, 06 May 2020 17:17:37 +0100

That's an interesting problem. I would use a tagged map where the key is
an integer offset in bytes from the beginning of the sparse array, and
the value would be the byte(s) from that position. 

i.e. 

2020({0: h'0107', 4000000000: h'15'}) 

D9 07E4           # tag(2020)
   A2             # map(2)
      00          # unsigned(0)
      42          # bytes(2)
         0107     # "\x01\a"
      1A EE6B2800 # unsigned(4000000000)
      41          # bytes(1)
         15       # "\x15" 

My thinking in this is that bit flags would tend to cluster together in
practice. 

It does have one problem in that it is possible to create overlapping
byte sequences. 

The decoder would not need to allocate much space. 

Cheers, 

Kio 

On 2020-05-06 16:38, Carsten Bormann wrote:

> CBOR mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cbor

---

From: [email-masked] (Dale R. Worley)
Date: Wed, 06 May 2020 22:16:29 -0400

Carsten Bormann <[email-masked]> writes:
> JFYI: Interesting discussion in core/netmod about potentially needing
> to represent sparse bit sets.  Anything we (cbor WG) can contribute to
> that?

One common representation for sparse bit sets is the list of indexes of
the 1 bits.  For this, the "Typed Arrays" proposal seems ideal.

I'm not sure this influences the Netmod discussion, though.

Dale

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 8 May 2020 08:48:07 +0200

If we go for this, as I’m proposing in <https://mailarchive.ietf.org/arch/msg/netmod/hRMjLIIpOyTNtmkv4yd3gyjd_gA>:

I think we should require that

— the offsets are (unsigned and) divisible by 8;
— the byte strings do not overlap.

I’m also not sure we wouldn’t want to require the offset/bitstring pairs to be in order, which would need an array instead of a map (as maps are not ordered).

Grüße, Carsten

> On 2020-05-06, at 18:17, Kio Smallwood <[email-masked]> wrote:
> 
> That's an interesting problem. I would use a tagged map where the key is an integer offset in bytes from the beginning of the sparse array, and the value would be the byte(s) from that position.
> 
> i.e.
> 
> My thinking in this is that bit flags would tend to cluster together in practice.
> 
> It does have one problem in that it is possible to create overlapping byte sequences.
>

---

From: Kio Smallwood <[email-masked]>
Date: Fri, 08 May 2020 10:37:43 +0100

Hi Carsten, 

Yes I agree, requiring an array makes more sense. I would prefer a byte
offset instead of a bit offset then you don't need to worry about the
divisible by eight constraint. 

Therefore the specification would be: 

- A tagged array containing: 

- An unsigned integer byte offset 

- followed by one or more contiguous bytes containing set bits 

- the next offset (must be strictly larger than the offset + length of
previous data item) 

- the next byte(s) 

- etc. 

e.g. 

2020([0, h'0107', 500000000, h'15']) 

The following example should result in an error: 

2020([0, h'0107', 1, h'01']) 

A case should be made that each offset+byte pair should have at least
one set bit. So this would be a valid bitfield that's all zeros: 

2020([]) 

Cheers, 

Kio 

On 2020-05-08 7:48, Carsten Bormann wrote:

> If we go for this, as I'm proposing in <https://mailarchive.ietf.org/arch/msg/netmod/hRMjLIIpOyTNtmkv4yd3gyjd_gA>:
> 
> -- the offsets are (unsigned and) divisible by 8;
> -- the byte strings do not overlap.
> 
> I'm also not sure we wouldn't want to require the offset/bitstring pairs to be in order, which would need an array instead of a map (as maps are not ordered).
> 
> Grüße, Carsten

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 8 May 2020 12:05:10 +0200

On 2020-05-08, at 11:37, Kio Smallwood <[email-masked]> wrote:
> 
> - the next offset (must be strictly larger than the offset + length of previous data item)
> 
> - the next byte(s)
> 
> - etc.
> 
> e.g.
> 
> A case should be made that each offset+byte pair should have at least one set bit. So this would be a valid bitfield that's all zeros:
> 
> 2020([])

Looks good.  Even better: make sure that an overlap cannot even be encoded.
The numbers in the array could be the number of bytes not sent that are presumed all zero.

So your first example would become:

2020([0, h'0107', 499999998, h'15’])

Or, actually, since the first zero becomes redundant now, 

2020([h'0107', 499999998, h'15’])

So the contents of the array would be byte strings or numbers that indicate gaps by giving the number of zero bytes.

Numbers should probably be positive (non-zero), and we could forbid adjacent numbers or trailing numbers.  Or we could just make that the preferred encoding and still allow them (including zeros); I don’t have a strong opinion.  (I’m not motivated enough to think about c14n now…)

[ASN.1 has the ability to indicate that the last byte in a bit string isn’t completely part of the bit string.  A trailing negative number could indicate that.  But I still haven’t seen a true use case for ASN.1 bit strings since I thought about that in 2013…]

Grüße, Carsten

---

From: Henk Birkholz <[email-masked]>
Date: Fri, 8 May 2020 12:19:24 +0200

Hi all,

quick note. I think it is sufficient to highlight "utilized bytes", it 
should also be expected that "a byte might not be used entirely", e.g. 
the last byte that might not be completely used by a bit string. That 
maps nicely to CBOR, simplifies the post-processing and would eliminate 
the additional use of a trailing negative number (please mind, not 
singed int).

That said, the "trailing negative number" is not a bad idea. I am just 
wondering, if we might want to "imply" a trailing negative number for 
bytes not entirely used for a bit string all the time, eliminating the 
need for that trailing negative number to be expressed, in general.

Viele Grüße,

Henk

---

From: Michael Richardson <[email-masked]>
Date: Fri, 08 May 2020 13:32:49 -0400

Carsten Bormann <[email-masked]> wrote:
    > Looks good.  Even better: make sure that an overlap cannot even be
    > encoded.  The numbers in the array could be the number of bytes not
    > sent that are presumed all zero.

At this point, we seem to have gotten to just doing Run-Length Encoding.

--
Michael Richardson <[email-masked]>, Sandelman Software Works
 -= IPv6 IoT consulting =-