[Cbor] Re: dCBOR: Normalization of Strings

[Joe Hildebrand <[e-mail]>]

Why would text in your application be in NFC form already?

Note that you have to at least check that whatever strings that needed to be normalized is in the correct format before trusting that the deterministic encoding was done correctly, which means every step in the process that relies on determinism is going to be doing this expensive check.

I'd need to know more about the particular application to have an opinion on whether all of the text needs to be normalized.  User-entered text that doesn't need to be compared against strings that were entered somewhere else probably don't need normalization, even for deterministic encoding.

— 
Joe Hildebrand

> On Jul 29, 2024, at 11:24 AM, Carsten Bormann <[e-mail]> wrote:
> 
> Hi Joe,
> 
> thank you for this interesting information.
> 
> I would expect that, in most cases, text in applications is already available in NFC form.  Only where that is not the case, normalization would actually be required; a high-performance application could rely on data at rest to be NFC.
> Similarly, the receiving application likely needs to ingest the information in NFC form, so there is no way around generating the NFC for ingestion.
> (In the environments dCBOR was designed for, Normalization always occurs in the process of deriving signing inputs from data at rest, so it is not just map keys.)
> This could pretty much nullify the advantages of NFD that you describe below.
> 
> Grüße, Carsten
> 
> 
>> On 2024-07-29, at 16:08, Joe Hildebrand <[e-mail]> wrote:
>> 
>> 1) NFC always requires memory allocation even for checking correctness.  NFD is much better for this sort of thing, and now that we have real fonts and text renderers that can do composition, it's almost always better for transmission.
>> 
>> 2) Normalization might only need to be applied to map keys.  It's a LOT more expensive than you expect, particularly if you choose NFC.
>> 
>> 
>> Explanation of 1) for those that that need it:
>> 
>> The "C" in "NFC" stands for "composition".  It requires strings like "ä" to be stored as U+00E4 (LATIN SMALL LETTER A WITH DIAERESIS) rather than U+0061 (LATIN SMALL LETTER A) followed by U+0308 (COMBINING DIAERESIS).  But since there might be multiple combining characters in play, each of which must be in the correct order, the NFC algorithm is to first break U+00E4 into U+0061 U+0308, then sort all of the combining characters, then recombine everything that is possible.  There's no way to just iterate through a string and determine that it is correct without breaking things apart and recombining them.
>> 
>> NFD does the "break apart" and "order" steps of NFC, but does not do the recombination.  Therefore, you can iterate through a string, see if anything can be broken apart or is an out of order combining character without having to modify the string or allocate memory when validating.  This turns out to be a MAJOR performance win in practice.  For this win to show up, you often need a validate() routine instead of doing "foo".normalize('NFD') === "foo", but it's at least possible.
>> 
>> — 
>> Joe Hildebrand
>> 
>>> On Jul 29, 2024, at 12:39 AM, Wolf McNally <[e-mail]> wrote:
>>> 
>>> All,
>>> 
>>> I’d like your comment on a proposed addition to dCBOR [1]:
>>> 
>>> • Encoders MUST only serialize text strings that are in Unicode Normalization Form C (NFC). [2]
>>> • Decoders MUST require that deserialized text strings are in NFC.
>>> 
>>> This rule is comparable to dCBOR’s mandate for numerical reduction, as it applies to one of the most common used data types, and closes a frequently-discussed [3] determinism loophole regarding Unicode strings having more than one equivalent way to encode the same semantics. For example:
>>> 
>>> 'e\u0301'  # 'e' followed by combining acute accent
>>> '\u00E9'   # 'é' as a single character (the normalized form of this character)
>>> 
>>> These strings are canonically equal but encoded differently, breaking determinism if encoded by different agents without the proposed rule.
>>> 
>>> I have verified that there are readily-available ways to convert strings to NFC in C/C++ (using ICU or Boost libraries), Swift (using Foundation’s `precomposedStringWithCanonicalMapping`), Rust (using the `unicode-normalization` crate), JavaScript (using `String.prototype.normalize`), and PHP (using the `Normalizer` class). Several of these languages also have streamlined APIs for efficiently detecting whether a string is in NFC, which is useful for decoders. Those without such an API can simply compare a string being deserialized to a re-normalized copy.
>>> 
>>> I think it’s important to note that text strings in ASCII and Latin-1 are already necessarily in NFC, and the normalization rules are designed to be efficient in such common cases.
>>> 
>>> [1] dCBOR: A Deterministic CBOR Application Profile
>>> https://datatracker.ietf.org/doc/draft-mcnally-deterministic-cbor/
>>> 
>>> [2] Unicode Standard Annex #15: Unicode Normalization Forms
>>> https://unicode.org/reports/tr15/
>>> 
>>> [3] Discussion on Unicode normalization as it relates to canonical JSON.
>>> https://esdiscuss.org/topic/json-canonicalize#content-3
>>> 
>>> ~ Wolf
>>> _______________________________________________
>>> CBOR mailing list -- [e-mail]
>>> To unsubscribe send an email to [e-mail]
>> 
>> _______________________________________________
>> CBOR mailing list -- [e-mail]
>> To unsubscribe send an email to [e-mail]
>