Re: [Cbor] Proposal for Deterministic CBOR (dCBOR) discussion at May 17th meeting

[Wolf McNally <[e-mail]>]

Carsten,

I should also add that between the integer representations and BIGNUM is the possibility of encoding large integer values as floats with no fractional part. So for example, 2^100, while not representable as a binary integer, is representable with no loss of accuracy as a floating point value (fa71800000). This is my current edit:

## Reduction of Floating Point Values to Integers

While there is no requirement that dCBOR codecs implement support for floating point numbers, dCBOR codecs that do support them MUST reduce floating point values with no fractional part to the integer value that can accurately represent it in the fewest bits. If a numeric value has a fractional part or an exponent that takes it out of the range of representable integers, then it SHALL be encoded as a floating point value. If it cannot be represented as a floating point value, then it SHALL be encoded as a BIGNUM by encoders that support them.

For the unsigned integers, from most to least preferred:

~~~
UInt8:  [0 ... 2^8 - 1]      [0 ... 255]
UInt16: [2^8 ... 2^16 - 1]   [256 ... 65535]
UInt32: [2^16 ... 2^32 - 1]  [65536 ... 4294967295]
UInt64: [2^32 ... 2^64 - 1]  [4294967296 ... 18446744073709551615]
Float: [2^64 ...]            [18446744073709551616 ...]
BIGNUM: [2^64 ...]           [18446744073709551616 ...]
~~~

For the signed integers, from most to least preferred:

~~~
Int8:   [-2^7 … 2^7 - 1]        [-128, 127]
Int16:  [-2^15 … 2^15 - 1]      [-32768, 32767]
Int32:  [-2^31 … 2^31 - 1]      [-2147483648, 2147483647]
Int64:  [-2^63 … 2^63 - 1]      [-9223372036854775808, 9223372036854775807]
Float:  [… -2^63 - 1 U 2^63 …]  [… -9223372036854775809 U 9223372036854775808 …]
BIGNUM: [… -2^63 - 1 U 2^63 …]  [… -9223372036854775809 U 9223372036854775808 …]
~~~


> On May 8, 2023, at 3:09 PM, Wolf McNally <[e-mail]> wrote:
> 
> Carsten,
> 
> Thank you for experimenting with this proposal. In recoding your tests in my Swift test harness, I realize that I left an ambiguity in the spec that you interpreted fairly the way I wrote it, but not the way I meant.
> 
> I wrote:
> 
>> While there is no requirement that dCBOR codecs implement support for floating point numbers, dCBOR codecs that do support them MUST reduce floating point values with no fractional part to the smallest integer value that can accurately represent it.
> 
> This resulted in your tests choosing BIGNUM representations with a smaller encoded representation. What I actually meant was to choose the representation with the smallest *maximum* number of represented bits. Since BIGNUM is arbitrarily large, it is least-preferred regardless of its serialized size.
> 
> The downside is that some BIGNUM representations with smaller serializations will not be used. The upside is that implementers do not have to support every size of serialization; in particular they do not have to support BIGNUM (as my Swift implementation currently does not) and in fact implementations on constrained hardware don’t even have to support 64-bit integers if they don’t need to.
> 
> For the unsigned integers:
> 
> UInt8: [0 ... 2^8 - 1] [0 ... 255]
> UInt16: [2^8 ... 2^16 - 1] [256 ... 65535]
> UInt32: [2^16 ... 2^32 - 1] [65536 ... 4294967295]
> UInt64: [2^32 ... 2^64 - 1] [4294967296 ... 18446744073709551615]
> BIGNUM: [2^64 ...] [18446744073709551616 ...]
> 
> For the signed integers:
> 
> Int8: [-2^7 … 2^7 - 1] [-128, 127]
> Int16: [-2^15 … 2^15 - 1] [-32768, 32767]
> Int32: [-2^31 … 2^31 - 1] [-2147483648, 2147483647]
> Int64: [-2^63 … 2^63 - 1] [-9223372036854775808, 9223372036854775807]
> BIGNUM: [… -2^63 - 1 U 2^63 …] [… -9223372036854775809 U 9223372036854775808 …]
> 
> So none of the examples you gave for your Ruby implementation actually require BIGNUM, so according to the spec the way I meant it, they MUST NOT use it. Here are the same test cases in Swift:
> 
>> XCTAssertEqual((0.0).cborData.hex, "00")
>> XCTAssertEqual((1).cborData.hex, "01")
>> XCTAssertEqual((1.0).cborData.hex, "01")
>> XCTAssertEqual((1.1).cborData.hex, "fb3ff199999999999a")
>> XCTAssertEqual((1.5).cborData.hex, "f93e00")
>> XCTAssertEqual((1.099609375).cborData.hex, "f93c66")
>> 
>> XCTAssertEqual(pow(2.0, 31).cborData.hex, "1a80000000")
>> XCTAssertEqual(2147483648.cborData.hex, "1a80000000")
>> 
>> XCTAssertEqual((pow(2.0, 32) - 1).cborData.hex, "1affffffff")
>> XCTAssertEqual(4294967295.cborData.hex, "1affffffff")
>> 
>> XCTAssertEqual(pow(2.0, 32).cborData.hex, "1b0000000100000000")
>> XCTAssertEqual(UInt64(4294967296).cborData.hex, "1b0000000100000000")
>> 
>> XCTAssertEqual((pow(2.0, 33) - 1).cborData.hex, "1b00000001ffffffff")
>> XCTAssertEqual(UInt64(8589934591).cborData.hex, "1b00000001ffffffff")
>> 
>> XCTAssertEqual(pow(2.0, 33).cborData.hex, "1b0000000200000000")
>> XCTAssertEqual(UInt64(8589934592).cborData.hex, "1b0000000200000000")
>> 
>> XCTAssertEqual((pow(2.0, 40) - 1).cborData.hex, "1b000000ffffffffff")
>> XCTAssertEqual(UInt64(1099511627775).cborData.hex, "1b000000ffffffffff")
>> 
>> XCTAssertEqual(pow(2.0, 40).cborData.hex, "1b0000010000000000")
>> XCTAssertEqual(UInt64(1099511627776).cborData.hex, "1b0000010000000000")
>> 
>> XCTAssertEqual((pow(2.0, 48) - 1).cborData.hex, "1b0000ffffffffffff")
>> XCTAssertEqual(UInt64(281474976710655).cborData.hex, "1b0000ffffffffffff")
>> 
>> XCTAssertEqual(pow(2.0, 48).cborData.hex, "1b0001000000000000")
>> XCTAssertEqual(UInt64(281474976710656).cborData.hex, "1b0001000000000000")
>> 
>> XCTAssertEqual((pow(2.0, 48) + 1).cborData.hex, "1b0001000000000001")
>> XCTAssertEqual(UInt64(281474976710657).cborData.hex, "1b0001000000000001")
>> 
>> XCTAssertEqual((pow(2.0, 48) + pow(2.0, 25)).cborData.hex, "1b0001000002000000")
>> XCTAssertEqual(UInt64(281475010265088).cborData.hex, "1b0001000002000000")
> 
> 
> A theoretical “big float” type would similarly be less-preferred than a 64-bit floating point encoding.
> 
> On another related topic, one potential downside of numerical reduction that I haven’t mentioned is that implementations that support floating point also need to have minimal support for 16-bit floating point values. By “minimal” I mean the ability to downcast 32-bit floats to 16-bit, retrieve the bit pattern, and upcast them again. Swift has a fully-featured native Float16 type, but it actually doesn’t work on the Intel family of processors, and since many Macs still use them I ended up coding a minimal implementation. Rust does not have a built-in `f16` type, but does have minimal support for it via a 3rd-party crate. Of course, I think most CBOR implementations already support 16-bit float serialization as they expect to read it. dCBOR introduces the additional requirement that they be able to write it.
> 
> ~ Wolf
> 
> 
>> (2**32).to_dcbor.hexs
>> => "c2 45 01 00 00 00 00"
> 
> 
>> On May 8, 2023, at 1:09 PM, Carsten Bormann <[e-mail]> wrote:
>> 
>> Hi Christopher,
>> 
>> Thank you for this proposal.
>> 
>> I will be on vacation on the 17th (from this Friday), so I’ll send some comments ahead on the list.
>> 
>>> ## Numerical Reduction
>>> 
>>> Proposal: All numbers MUST be reduced to the smallest possible representation. Failure to do so is a well-formness error.
>> 
>> (I don’t think we want to change the term “well-formedness”.  I’d say this is a validity error.)
>> 
>> I went ahead and implemented what I think this is in the cbor-dcbor gem.
>> 
>>  gem install cbor-dcbor
>> 
>> and go play.
>> 
>> Here are a few examples (*):
>> 
>> $ irb -rcbor-dcbor
>> 
>>>> 0.to_dcbor.hexs
>> => "00"
>>>> 1.to_dcbor.hexs
>> => "01"
>>>> 1.0.to_dcbor.hexs
>> => "01"
>>>> 1.1.to_dcbor.hexs
>> => "fb 3f f1 99 99 99 99 99 9a"
>>>> 1.5.to_dcbor.hexs
>> => "f9 3e 00"
>> 
>> So we see the usual problems that decimal fractions only hit the short binary numbers by accident.  (Asking the application to find the closest number that is encodable as a float16, as in 
>>>> 1.099609375.to_dcbor.hexs
>> => "f9 3c 66"
>> would probably require the application to care about the encoding length plus have a good understand what precision is actually desired.)
>> 
>>>> (2**31).to_dcbor.hexs
>> => "1a 80 00 00 00"
>>>> (2**32-1).to_dcbor.hexs
>> => "1a ff ff ff ff"
>>>> (2**32).to_dcbor.hexs
>> => "c2 45 01 00 00 00 00"
>> 
>> shows the transition from 1+4-byte ints (major type 0) to 1+1+4-byte bignums (tag 2, major type 2 inside).
>> 
>>>> (2**48-1).to_dcbor.hexs
>> => "c2 46 ff ff ff ff ff ff"
>>>> (2**48).to_dcbor.hexs
>> => "1b 00 01 00 00 00 00 00 00"
>> 
>> shows the transition back from 1+1+6 bignums to 1+8 ints.
>> 
>> Now there is an interesting interaction with floating point numbers here:
>> 
>>>> (2**31).to_f.to_dcbor.hexs
>> => "1a 80 00 00 00"
>>>> (2**31-1).to_f.to_dcbor.hexs
>> => "1a 7f ff ff ff"
>>>> (2**32-1).to_f.to_dcbor.hexs
>> => "1a ff ff ff ff"
>>>> (2**32).to_f.to_dcbor.hexs
>> => "fa 4f 80 00 00”
>>>> (2**33-1).to_f.to_dcbor.hexs
>> => "c2 45 01 ff ff ff ff”
>>>> (2**33).to_f.to_dcbor.hexs
>> => "fa 50 00 00 00"
>>>> (2**40-1).to_f.to_dcbor.hexs
>> => "c2 45 ff ff ff ff ff”
>>>> (2**40).to_f.to_dcbor.hexs
>> => "fa 53 80 00 00"
>>>> (2**48-1).to_f.to_dcbor.hexs
>> => "c2 46 ff ff ff ff ff ff"
>>>> (2**48).to_f.to_dcbor.hexs
>> => "fa 57 80 00 00”
>>>> (2**48+1).to_f.to_dcbor.hexs
>> => "1b 00 01 00 00 00 00 00 01"
>>>> (2**48+2**25).to_f.to_dcbor.hexs
>> => "fa 57 80 00 01"
>> 
>> I think this needs pretty strong test vectors, but was trivial to implement.
>> 
>>> * This includes the reference implementation at https://cbor.me 
>> 
>> (Another flag for this can easily be added.)
>> 
>>> * Some integer values (such as 1099511627775 [0xffffffffff]) can actually be larger than BIGNUM equivalents!
>> 
>> Which the above PoC code correctly handles.
>> 
>>> Alternative: The alternative would be to mandate that floats remain unchanged, which trends away from the suggestions in §4.2 of RFC 8949 for moving data to the shortest encoding possible and has the possibility of damaging determinism, but which matches some current implementations:
>>>   * Floats MUST be maintained as Floats, but otherwise all numbers MUST be reduced to the smallest possible representation. Failure to do so is a well-formness error.
>> 
>> This rule again creates tag2/tag3 numbers for unsigned values of 2**32 to 2**48-1.
>> 
>>> ## Adding dCBOR Support to Flagship Implementations and Tools
>>> 
>>> Proposal: Add a "deterministic" flag to existing implementations and tools such as https://cbor.me and QCBOR.
>> 
>> (The code behind cbor.me already has a “deterministic” flag which should be easy to export to the GUI.)
>> 
>>> * Requires work to implement, test, document, and maintain
>> 
>> I spent some 50 minutes on this so far (including this mail) :-)
>> 
>>> ## Bringing the dCBOR specification under purview of the CBOR Working Group and putting it on a track to RFC status.
>>> […]
>>> 
>>> * Would require active participation from the CBOR WG.
>> 
>> Indeed, we’d need to find out who else is interested in such a set of additional rules.
>> 
>> Note that there is a whole universe of potential additional rules in the tags, e.g. should 0("2013-03-21T20:04:00.000Z”) be converted to 0("2013-03-21T20:04:00Z”)?  Maybe even 0("2013-03-21T20:04Z”)?
>> What about float vs. int for tag 1?
>> 
>> Grüße, Carsten
>> 
>> 
>> (*)  Add this convenience function:
>> 
>> class String
>>  def hexs
>>    bytes.map{|x| "%02x" % x}.join(" ")
>>  end
>> end
>> 
>> to your .irbrc to play these examples.
>> 
>