BON8 support

[nlohmann]

In a recent Reddit discussion I learned about the BON8 format which is another binary format for JSON, but with a unique idea to exploit some characteristics of UTF-8 strings.

Maybe this format could be added as prototype to the library.

• specification
• optimized specification
• implementation

/cc @takev

[takev]

As discussed in the reddit post, I had updated the BON8 specification to handle small arrays and objects better.

I have now merged those changes to the main branch, and the "specification" link above post to the correct version.
The "optimized specification" will disappear when I am done working on that branch. The "implementation" is still based on the old specification and will be replaced when I merge the branch I am working on.

No more changes will be done to the codes and their meaning.

If there are other bugs in the specification, or things that are unclear, please don't forget to contact me and attempt to fix those issues.

[nlohmann]

I have some questions:

1. 0.0 has a compact encoding of 0xFC - but how is -0.0 encoded? As 0x8E 80 00 00 00?
2. How is {"a": "", "c": "d"} encoded: As 0x88 0x61 0xFF 0xFF 0x63 0xFF 0x64? (I am confused about the rules when to insert a 0xFF.

[takev]

-0.0 should be encoded as 0xfc. Mostly because 0.0 compares equal to -0.0, and has pretty limited impact.

The last "d" needs to be terminated with 0xff as well, due to it being at the end of the message.

Append 0xff when:

• The string is empty
• The string is the last thing in the message (also if the string is at the end of the last object or array).
• The string is followed by another string (also if the string is at the end of an object or array, which is followed by a string).

I will update the documentation to be more clear, maybe add a few examples.

[takev]

Okay, I relent.

Integers now have fitting ranges, and canonical representation is now optional.

Code Sequence	#	Type	Bits	Min	Max
90-b7	1	Positive integer		0	39
b8-c1	1	Negative Integer		-1	-10
c2-df 00-7f	2	Positive Integer (30 * 128)		40	3879
e0-ef 00-7f byte*1	3	Positive Integer	19	3880	528167
f0-f7 00-7f byte*2	4	Positive Integer	26	528168	67637031
c2-df c0-ff	2	Negative Integer (30 * 64)		-11	-1930
e0-ef c0-ff byte*1	3	Negative Integer	18	-1931	-264074
f0-f7 c0-ff byte*2	4	Negative Integer	25	-264075	-33818506

Extra rules

The rules below ensures minimum message size and consistency, which allows for cryptographically
signing of messages. All encoders MUST follow these rules.

• A message is a single value. Most often this value is of type Object or type Array.
• A string does not need to be terminated with an eos (0xff), if the ending of a string
  can be determined in other ways.
• String MUST end with eos (0xff) when:
  • The string is empty,
  • When the next byte in the message starts another string,
  • If there are no more bytes left in the message.
• Strings MUST be a valid UTF-8 encoded string.
• Strings MAY contain any Unicode code-point between U+0000 and U+10ffff.
• Integers and floating point numbers are stored most significant bits first (big endian).

Canonical Representation

The rules below ensure a minimum message and a consistent encoding between different
implementation. The canonical representation is consistent enough to be used for cryptographically
signing of data.

• The unicode string MUST be in Normalization Form C (NFC).
• Floating point negative zero, infinite and NaN MUST be encoded as binary32.
• NaN should be encoded as a 0x7f800001.
• Floating point numbers that can be converted to binary32 without loss
  of precision or range MUST be encoded as binary32.
• Strings, Integers, Arrays and Objects MUST be encoded with the least amount of bytes.
• The keys of an Object MUST be lexically ordered based on UTF-8 code-units.

[nlohmann]

Floating point numbers that can be converted to binary32 without loss of precision or range MUST be encoded as binary32.

Do you mean "float32" rather than "binary32"?

[takev]

In the IEEE 754-2008 standard, the 32-bit base-2 format is officially referred to as binary32.

[nlohmann]

Thanks for adjusting the integer ranges - I just committed the changes to the bon8 branch. The BON8 writer is nearly finished - there are likely bugs in it, but I would need more examples to find them. Do you have some test suite or list of examples for the corner cases?

And, just to clarify: You write "NaN should be encoded as a 0x7f800001." - I assume 0x7f800001 is a float, so the BON8 representation of NaN is 0x8e7f800001, right?

[takev]

Sorry, a bit late.

I do not have many tests yet. Sadly I have a lot of code to maintain the BON8 specification has a few examples in regard to strings.

The NaN should indeed be encoded as a 0x8e 0x7f 0x80 0x00 0x01. NaNs hopefully are not normal for data, so storing them as 5 bytes is hopefully fine.

[nlohmann]

FYI, I started a PR for BON8 support: #2998.