Subject: Re: Updated Binary Optimized Header Encoding Draft

From: Frédéric Kayser <[email-masked]>
Date: Thu, 15 Nov 2012 01:17:20 +0100

Hi,
could you precise some points regarding UTF-8 encoding ? 

"The next bit (E) indicates, when set, that the header field value contains UTF-8 encoded character content."

- is a BOM allowed?
- are there restrictions concerning Unicode Normalizations Forms, NFC is used most of the time but NFD could lead to smaller compressed results

And since UTF-8 is used why stick to generic zlib/deflate for compression?
UTF-8 encoding has some inherent characteristics http://en.wikipedia.org/wiki/UTF-8#Description
A compression algorithm aware of those would be more efficient than deflate, Huffman encoding in deflate is context unaware (order 0) contrary to PPM (Prediction by partial matching) based algorithms.

By today standards zlib/deflate is totally outdated: search window limited to 32k Bytes (can you imagine how ridiculous this is when used in nowadays PNG files, look what Google did in WebP lossless), it's dog slow to compress/decompress compared to LZ4, compressed size is far from being on par with LZMA or even bzip2, OK running an LZMA decoder is probably not the best thing to do on power and memory limited smartphones, but I wouldn't mind moving away from zlib/deflate for something closer to the compressed size vs. compression time Pareto frontier.

Regards
-- 
Frédéric Kayser

Le 3 oct. 2012 à 19:07, James M Snell a écrit :

> FYI.. I have submitted an updated draft for the proposed Binary Optimized Header Encoding mechanism for the http2 effort. 
> 
>   http://www.ietf.org/id/draft-snell-httpbis-bohe-01.txt
> 
> A number of fairly significant changes have been made:
> 
>   1. The codepage identifier for registered header tokens has been removed.
>   2. The Per-header flags field has been removed and replaced with specific individual bits to indicate character-based values and multiple values
>   3. Value lengths have been increased from max 16-bit length to a max 22-bit length. 
> 
> The encoding itself remains just as compact with these changes. With the http version header field, for example, requiring no more than 6 uncompressed bytes to represent.
> 
> As always, feedback is more than welcome.
> 
> - James

---

From: "Martin J. Dürst" <[email-masked]>
Date: Thu, 15 Nov 2012 14:00:09 +0900

Hello Frédéric,

> "The next bit (E) indicates, when set, that the header field value contains UTF-8 encoded character content."

It does not make any sense at all as an encoding signature (we already 
know it's UTF-8). In the (hopefully very rare) cases it's present, it 
should be taken as part of the data (i.e. a ZERO WIDTH NO-BREAK SPACE).

The "UTF-8 BOM" (it's actually not a BOM, because there's no need to 
distinguish byte orders in UTF-8) is used quite a bit as an encoding 
signature for whole files. For this use case, there are vastly differing 
opinions, from "extremely useful" (more on the Windows side) to "very 
bothering" (more on the Linux side).

But for fields in protocols and formats, it's totally unnecessary, I 
don't know of anybody who's using or pushing it, and as far as I know, 
the danger that it slips in is fortunately extremely low.

> - are there restrictions concerning Unicode Normalizations Forms,

There shouldn't be, because in some cases, it may be necessary to allow 
both forms. Imagine a service that converts data from one of these forms 
to the other.

On the other hand, recommending that NFC be used when there's a choice 
is a good idea (it will mostly happen even without this recommendation, 
but the recommendation will address questions like the ones in your email.

> NFC is used most of the time but NFD could lead to smaller compressed results

Do you have any data to back this up, or is this just a guess?

NFC (Composed) is by definition always at least as short as NFD 
(Decomposed). It is probably not impossible to construct data for which 
NFD compresses better than NFC (*), but I'm having a very hard time 
imagining that NFD would compress better than NFC for a wide range of data.

> UTF-8 encoding has some inherent characteristics http://en.wikipedia.org/wiki/UTF-8#Description

(see also http://www.sw.it.aoyama.ac.jp/2012/pub/IUC11-UTF-8.pdf, a 
paper of mine from 1997 showing how this allows easy heuristic 
distinction between UTF-8 and other encodings)

> By today standards zlib/deflate is totally outdated: search window limited to 32k Bytes (can you imagine how ridiculous this is when used in nowadays PNG files, look what Google did in WebP lossles…

Do you have any particular algorithm in mind? Ideally something that is 
well established, and works not only for UTF-8. Otherwise, we need two 
separate algorithms, one for UTF-8 and one for the rest of the data.

Regards,   Martin.

P.S. (*): One line worth trying may be a language where there is a 
strong correlation between a vowel and the previous consonant, and also 
a strong correlation between the accent (e.g. tone mark) on the vowel 
and following consonants.

Because NFD treats the vowel and the accent as as separate characters, 
both of these correlations can be picked up independently. On the other 
hand, in the case of NFC, the vowel and the accent are just one 
precomposed character, which may make it more difficult to pick up the 
correlations quickly.

But this is highly speculative, and depends quite a bit on the length of 
the input and the size of the tables used,...

---

From: Frédéric Kayser <[email-masked]>
Date: Thu, 15 Nov 2012 10:58:44 +0100

Hello Martin,
I have a short French text sample here, it's a small extract from « Le tour du monde en quatre-vingts jours » ("Around the World in Eighty Days") by Jules Verne.

The bzip2 compressed version of the NFD encoded text is smaller by 4 bytes.
Using gzip it looks like a draw but in fact the Deflate stream itself is 4 bits shorter.
In the other hand when using xz (lzma2) NFC gives a better result.

2553 tdm80j-french-utf8-nfc.txt
2625 tdm80j-french-utf8-nfd.txt

1312 tdm80j-french-utf8-nfc.txt.bz2
1308 tdm80j-french-utf8-nfd.txt.bz2

1352 tdm80j-french-utf8-nfc.txt.gz
1352 tdm80j-french-utf8-nfd.txt.gz

defdb -s tdm80j-french-utf8-nfc.txt.gz
10671 bits

defdb -s tdm80j-french-utf8-nfd.txt.gz
10667 bits

Compressed files are enclosed in the zip archive attached to this email.

Regards
-- 
Frédéric Kayser

Le 15 nov. 2012 à 06:00, Martin J. Dürst a écrit :

> NFC (Composed) is by definition always at least as short as NFD (Decomposed). It is probably not impossible to construct data for which NFD compresses better than NFC (*), but I'm having a very hard time imagining that NFD would compress better than NFC for a wide range of data.

...

> P.S. (*): One line worth trying may be a language where there is a strong correlation between a vowel and the previous consonant, and also a strong correlation between the accent (e.g. tone mark) on the vowel and following consonants.
> 
> Because NFD treats the vowel and the accent as as separate characters, both of these correlations can be picked up independently. On the other hand, in the case of NFC, the vowel and the accent are just one precomposed character, which may make it more difficult to pick up the correlations quickly.
> 
> But this is highly speculative, and depends quite a bit on the length of the input and the size of the tables used,...

---

From: Willy Tarreau <[email-masked]>
Date: Thu, 15 Nov 2012 11:28:52 +0100

Hi Frederic,

> Compressed files are enclosed in the zip archive attached to this email.

Do not forget that the most important for HTTP is not the compression
ratio but the compression speed. If you need a whole datacenter to
compress 1000 streams, nobody will use it. If the compression induces
delays, it will not be used either. If you check around, you'll see that
HTTP compression engines right now compress at gzip-1 to achieve the best
compression speed allowed on HTTP. And I agree with your comment in a
previous mail that gzip is totally outdated. I'd like to have much faster
compression algos such as LZ4, fastlz, etc... which are 10-100 times faster
than gzip for around the same compression ratios as gzip-1.

Cheers,
Willy

---

From: Roberto Peon <[email-masked]>
Date: Thu, 15 Nov 2012 06:31:48 -0800

Remember the CRIME exploit, guys. Stream compressors aren't very safe to
use...

-=R
On Nov 15, 2012 2:30 AM, "Willy Tarreau" <[email-masked]> wrote:

> > I have a short French text sample here, it's a small extract from « Le
> tour du monde en quatre-vingts jours » ("Around the World in Eighty Days")
> by Jules Verne.
> >

---

From: Nico Williams <[email-masked]>
Date: Tue, 20 Nov 2012 15:04:56 -0600

I don't recommend using NFD. My rain for this is simple: the majority of
input modes produce NFC, thus too many libraries were coded to deal
primarily or only with pre-composed sequences -- throwing NFD at then can
cause trouble, so I'd rather avoid it.

(My experience here comes from HFS+'s conversion of file names to NFD on
create.)

Nico
--

---

From: Frédéric Kayser <[email-masked]>
Date: Wed, 21 Nov 2012 15:55:08 +0100 (CET)

Effectively, I have noticed some odd behaviour, for instance search of words containing diacritics does not work if the text is in NFD since when typed the search string is usually in NFC (tested in many text editors and web browsers).

Regards
-- 
Frédéric Kayser

----- Mail original -----
De: "Nico Williams" <[email-masked]>
À: "Frédéric Kayser" <[email-masked]>
Cc: "HTTP Working Group" <[email-masked]>, "Martin J. Dürst" <[email-masked]>
Envoyé: Mardi 20 Novembre 2012 22:04:56
Objet: Re: UTF-8 NFC vs NFD compression, French sample (was: Updated Binary Optimized Header Encoding Draft)

I don't recommend using NFD. My rain for this is simple: the majority of input modes produce NFC, thus too many libraries were coded to deal primarily or only with pre-composed sequences -- throwing NFD at then can cause trouble, so I'd rather avoid it. 

(My experience here comes from HFS+'s conversion of file names to NFD on create.) 

Nico 
--

---

From: Nico Williams <[email-masked]>
Date: Wed, 21 Nov 2012 09:17:09 -0600

On Wednesday, November 21, 2012, Frédéric Kayser wrote:

> Effectively, I have noticed some odd behaviour, for instance search of
> words containing diacritics does not work if the text is in NFD since when
> typed the search string is usually in NFC (tested in many text editors and
> web browsers).

Exactly.  Now, we are talking about intra-protocol elements, but even so,
I'd rather focus on alternative ways to compress than this one.