Subject: Header Serialization Discussion

From: James M Snell <[email-masked]>
Date: Sat, 13 Apr 2013 15:01:24 -0700

Ok... so I've implemented HeaderDiff serialization [1] in java [2]...
just the serialization so far, will do deserialization early next
week. The implementation is very rough and definitely needs
improvement / optimization but it's functional enough to start from.

[1] http://tools.ietf.org/html/draft-ruellan-headerdiff-00
[2] https://github.com/jasnell/http2/tree/master/src/snell/http2/headers/headerdiff

I know that Roberto is working on refinements to his own concept of
the delta header serialization and hopefully he'll be sharing those
thoughts soon, but I wanted to get my current thoughts captured for
discussion.

The HeaderDiff approach is straightforward and effective and makes
efficient use of available bits. It's variable length integer syntax
is a bit complicated with the notion of bit-prefix lengths but once
you've got it it's easy to understand what's going on. The
implementation is a bit less complicated than delta, which is good and
I like that there's no "Header Group" notion. Headers are either on or
off per request. There are several concerns, however.

  - The true utility of the common prefix length mechanism is
questionable. Aside from the potential security risks, I questioning
just how effective it's going to be in practice. (What header fields
do we expect to actually use it in practice?)

  - The fact that items are never removed from the Name Table is
concerning and poses a potential security risk. The the decompressor
is forced to maintain a symbol table for every header name it
encounters, a malicious compressor could cause overruns by sending a
high number of junk header names. The compressor ought to be able to
treat the Name Table as an LRU, and ought to be able to place strict
limits on it's size, just as it does with the Header Table. Delta does
not have this issue because it's name indices are already tied to the
LRU.

With HeaderDiff in mind, I'm thinking about how we can bring
HeaderDiff and Delta together and roll in the additional concepts of
Typed Codecs. Here's what I have in mind.

Syntax:

The serialization syntax borrows concepts from both HeaderDiff and
Delta and is divided into two parts: Basic Header Serialization and
Value Serialization.

As with Delta currently, there are four operation codes (opcodes),
represented by two-bit identifiers. Each op code has a single-bit
"ephemeral flag". Operations are serialized into batches of no more
than 32 instances.

  00 0 00000 { HEADER }

The first two most significant bits...

  00 = Index (what Delta calls "Toggl")
  01 = Index Range (what Delta calls "Trang")
  10 = Clone
  11 = Literal (what Delta calls "KVSto")

The third most significant bit is the ephemeral toggle

  0 = Persist (the header value is to be persisted in the LRU table)
  1 = Ephemeral (the header value is not to be persisted in the LRU table)

The remaining five bits specify the number of distinct instances in
this batch. This counter is 0-based, so 0x0 = 1 item in the batch,
0x1F = 32 items in the batch.

The ephemeral flag is ignored for opcodes 00 and 01.

Indexed headers are identified by a single byte index value.

  0 0000000

The first most significant bit indicates whether or not the index is
part of the static header dictionary or lru cache.

  0 = LRU
  1 = Static

This gives us a strict maximum of 128 storage slots for the LRU.
That's limited *on purpose* to place strictly finite constraints on
the amount of state any single compressor can require. This also
ensures that we are always able to encode indices using only a single
byte.

As for state management, we would essentially use the Header Diff
model minus the separate Name Table. That is, there is no persistent
Header Group in use; just the Header Table. State management depends
on the specific opcodes used. State management occurs as the headers
are encountered in the serialized header block.

  00 = Use an indexed header instance from the header table for this request
  01 = Use multiple sequentially indexed header instances from the
header table for this request
  10 = Use a new value for an already existing header name, index
references an existing header from the table, persist the new value if
the ephemeral bit is not set.
  11 = Use a new key and value for this request. Persist the new pair
if the ephemeral bit is not set.

So, for example, the serialization:

  00000000 10000000 =
    Use index #0 from the static dictionary

  00000001 10000000 00000001 =
    Use index #0 from the static dictionary and index #1 from the lru cache

  01000001 10000000 10000001 00000001 00000010 =
    Use indices #0-#1 from the static dictionary and indices #1-#2
from the lru cache

  10000000 10000000 {VALUE}
    Provide a new value for the header name identified by index #0 in
the static dictionary and persist the value in the lru cache

  10100000 10000000 {VALUE}
    Provide a new value for the header name identified by index #0 in
the static dictionary but do not persist the value in the lru cache

Non-ephemeral items are pushed into the next available slot in the
LRU. Once all available slots have been used, the indices rotate. The
LRU can also be limited by storage space. As storage space is
required, the least recently items are dropped. Keeping in mind that
there are only 128 available storage slots, it will be important for
compressors to be selective about which fields are persisted.

(note.. the LRU is really a "least recently written" cache.. not
"least recently used"...)

These values are tracked only for the current message. There is no
Header Group as currently defined by Delta so there is no need to
track whether or not any given header is currently on or off. It's
either referenced for this request or it's not.

If there are more than 32 instances of any single opcode per
serialized header block (which is unlikely), a single opcode may
appear multiple times within the serialized block.

As far as Value serialization is concerned... As I have discussed
previously, I have been looking at support for four distinct value
types, each represented by their own two-bit identifier. As I will
explain further in a second, these types are represented using the two
most significant bits in a byte:

  00 = Text
  01 = Number
  10 = Date Time
  11 = Binary

Text can be either UTF-8 or ISO-8859-1, indicated by a single bit flag
following the type code. All text strings are prefixed by it's length
given as an unsigned variant length integer
Numbers are encoded as unsigned variable length integers.
Date Times are encoded as Numbers representing the number of seconds
that have passed since the epoch (GMT).
Binary data is encoded as raw binary octets prefixed by an unsigned
variable length integer specifying the number of bytes.

Any single header value instance can consist of up to 32 distinct
value tokens. The number of tokens is specified using the 5 least
significant bytes of type type flag.

For instance:

  00000000 00000001 01100001 =
    A single ISO-8859-1 Text value with length = 1

  00100000 00000001 01100001  =
    A single UTF-8 Text value with length = 1

  00100001 00000001 01100001 00000001 01100010 =
    Two UTF-8 Text values, each with length = 1

  01000000 00000001 =
    A single Number value

  10000000 00000001 =
    A single Date value (1 second after the epoch)

  11000000 00000001 00000001 =
    A single Raw Binary value

For ISO-8859-1 Text, the Static Huffman Code used by Delta would be
used for the value. If we can develop an approach to effectively
handling Huffman coding for arbitrary UTF-8, then we can apply Huffman
coding to that as well.

For the Number and DateTime serialization:

  - 16-bit numbers serialize with a strict maximum of 3 bytes
  - 32-bit numbers serialize with a strict maximum of 5 bytes.
  - 64-bit numbers serialize with a strict maximum of 10 bytes.
  - Date Times will serialize with five bytes for the reasonably
relevant future, then six bytes for quite some time after that. Dates
prior to the epoch cannot be represented.

In order to properly deal with the backwards compatibility concerns
for HTTP/1, there are several important rules for use of Typed Codecs
in HTTP headers:

1. Headers must be explicitly defined to use the new header types. All
existing HTTP/1 headers, then, will continue to be required to be
represented as ISO-8859-1 Text unless their standard definitions are
updated. The HTTP/2 specification would update the definition of
specific known headers (e.g. content-length, date, if-modified-since,
etc).

2. Extension headers that use the typed codecs will have specific
normative transformations to ISO-8859-1 defined.
    a. UTF-8 Text will be converted to ISO-8859-1 with extended
characters pct-encoded
    b. Numbers will be converted to their ASCII equivalent values.
    c. Date Times will be converted to their HTTP-Date equivalent values.
    d. Binary fields will be Base64-encoded.

3. There will be no normative transformation from ISO-8859-1 values
into the typed codecs. Implementations are free to apply
transformation where those impls determine it is appropriate, but it
will be perfectly legal for an implementation to pass a text value
through even if it is known that a given header type has a typed codec
equivalent (for instance, Content-Length may come through as a number
or a text value, either will be valid). This means that when
translating from HTTP/1 -> HTTP/2, receiving implementations need to
be prepared to handle either value form.

This approach combines what I feel are the best concepts from
HeaderDiff and Delta and provides simple, straightforward header
serialization and state management. Obviously, lots of testing is
required, however.

As always, thoughts/opinions/gripes are appreciated.

- James

---

From: RUELLAN Herve <[email-masked]>
Date: Mon, 15 Apr 2013 15:28:36 +0000

> -----Original Message-----
> From: James M Snell [mailto:[email-masked]]
> Sent: dimanche 14 avril 2013 00:01
> To: [email-masked]
> Subject: Header Serialization Discussion
> 
> just the serialization so far, will do deserialization early next week. The
> implementation is very rough and definitely needs improvement /
> optimization but it's functional enough to start from.
> 
> [2]
> https://github.com/jasnell/http2/tree/master/src/snell/http2/headers/hea
> derdiff
> 
> I know that Roberto is working on refinements to his own concept of the
> delta header serialization and hopefully he'll be sharing those thoughts soon,
> but I wanted to get my current thoughts captured for discussion.
> 
> The HeaderDiff approach is straightforward and effective and makes efficient
> use of available bits. It's variable length integer syntax is a bit complicated
> with the notion of bit-prefix lengths but once you've got it it's easy to
> understand what's going on. The implementation is a bit less complicated
> than delta, which is good and I like that there's no "Header Group" notion.
> Headers are either on or off per request. There are several concerns,
> however.
> 
>   - The true utility of the common prefix length mechanism is questionable.
> Aside from the potential security risks, I questioning just how effective it's
> going to be in practice. (What header fields do we expect to actually use it in
> practice?)

Common prefixes are very efficient for URLs: the paths often share some common part at their beginnings. They are also useful for other type of data such a date and integers, but these could be optimized using typed codecs.

>   - The fact that items are never removed from the Name Table is concerning
> and poses a potential security risk. The the decompressor is forced to
> maintain a symbol table for every header name it encounters, a malicious
> compressor could cause overruns by sending a high number of junk header
> names. The compressor ought to be able to treat the Name Table as an LRU,
> and ought to be able to place strict limits on it's size, just as it does with the
> Header Table. Delta does not have this issue because it's name indices are
> already tied to the LRU.

True, some kind of mechanism should be added to prevent memory overrun of the Name Table. A simple one is to simply limit the number of entries that can be added to the table.

> With HeaderDiff in mind, I'm thinking about how we can bring HeaderDiff and
> Delta together and roll in the additional concepts of Typed Codecs. Here's
> what I have in mind.
> 
[snip]

My main concern with your proposal is about doing the LRU on both the encoder and the decoder. 
I'd really like to keep the decoder as simple as possible, and so keeping all the buffer management on the encoder side is a real win for me.
In addition, the asymmetry means that the encoder is free to do whatever buffer management it wants. LRU is a very good default buffer management scheme, however I think there are cases where some clever scheme could beat it.

> For ISO-8859-1 Text, the Static Huffman Code used by Delta would be used
> for the value. If we can develop an approach to effectively handling Huffman
> coding for arbitrary UTF-8, then we can apply Huffman coding to that as well.
> 
>   - Date Times will serialize with five bytes for the reasonably relevant future,
> then six bytes for quite some time after that. Dates prior to the epoch cannot
> be represented.
> 
> In order to properly deal with the backwards compatibility concerns for
> HTTP/1, there are several important rules for use of Typed Codecs in HTTP
> headers:
> 
> updated. The HTTP/2 specification would update the definition of specific
> known headers (e.g. content-length, date, if-modified-since, etc).
> 
> 2. Extension headers that use the typed codecs will have specific normative
> transformations to ISO-8859-1 defined.
>     a. UTF-8 Text will be converted to ISO-8859-1 with extended characters
> pct-encoded
> 3. There will be no normative transformation from ISO-8859-1 values into the
> typed codecs. Implementations are free to apply transformation where
> those impls determine it is appropriate, but it will be perfectly legal for an
> implementation to pass a text value through even if it is known that a given
> header type has a typed codec equivalent (for instance, Content-Length may
> come through as a number or a text value, either will be valid). This means
> that when translating from HTTP/1 -> HTTP/2, receiving implementations
> need to be prepared to handle either value form.

I really like your approach to typed codecs. And while it has been ruled out for the first implementation draft, I think it's useful to pursue as an improvement for a further version of the header compression mechanism. 
I'm willing to do experimentation on it.

Hervé.

> This approach combines what I feel are the best concepts from HeaderDiff
> and Delta and provides simple, straightforward header serialization and state
> management. Obviously, lots of testing is required, however.
>

---

From: James M Snell <[email-masked]>
Date: Mon, 15 Apr 2013 08:55:01 -0700

> Common prefixes are very efficient for URLs: the paths often share some common part at their beginnings. They are also useful for other type of data such a date and integers, but these could be opt…

I generally prefer the typed codecs for dates and integers. I'm
struggling to see what, beyond URLs, the prefixes will be useful for,
really. I mean, I get the theory, I understand their use, but I'm just
not convinced how often it will be practical outside of the request
URI. I don't want to incur the performance hit of calculating the
longest common prefix for every text header if doing so just isn't
going to be useful. What I'm considering is writing my encoder so that
it only calculates the common prefix for the :path header, ignoring it
for everything else.

> In addition, the asymmetry means that the encoder is free to do whatever buffer management it wants. LRU is a very good default buffer management scheme, however I think there are cases where some…

Well, it's not so much an LRU cache as a "least recently written"
queue. The buffer essentially consists of 128 memory slots. These are
assigned in order and rotate, with used slots deallocated and
reassigned as the buffer fills past it's limit. The encoder, then,
needs to be selective about just what it decides to assign to the
buffer. So long as an implementation follows the proper assignment
order, the specific implementation does not matter.

> I'm willing to do experimentation on it.

Excellent. Once we have the basic header encoding down in the spec I
plan on writing up a more formal I-D proposal with spec language for
the typed codecs. However, I think that this particular aspect is
going to remain fairly stable now.

- James

---

From: "Adrien W. de Croy" <[email-masked]>
Date: Mon, 15 Apr 2013 23:44:08 +0000

------ Original Message ------
From: "James M Snell" <[email-masked]>
>>>questionable.
>>  Common prefixes are very efficient for URLs: the paths often share 
>>some common part at their beginnings. They are also useful for other 
>>type of data such a date and integers, but these could be optimized 
>>using typed codecs.
>>
>
>URI.

Referer as well

Adrien

---

From: Frédéric Kayser <[email-masked]>
Date: Tue, 16 Apr 2013 04:23:41 +0200

Hello,
If text fields can effectively be encoded as UTF-8 would it be wise to use it to send IRIs (RFC3987)?
without punycode:
http://xn--acadmie-franaise-npb1a.fr/ vs. http://académie-française.fr/
http://www.xn--cigacz-2ib.pl/ vs. http://www.ścigacz.pl/
http://xn--rlcuo9h.xn--wkc4axeaevb3oqbg.xn--xkc2al3hye2a/ vs. http://தளம்.ஆள்களமையம்.இலங்கை/
http://xn--mgbggrfi2ikdb7d.xn--mgberp4a5d4ar/ vs. http://مركزالتسجيل.السعودية/

and without percent encoding:
zdj%C4%99cia vs. zdjęcia
g%C3%B6r%C3%BCnt%C3%BC vs. görüntü

I wouldn't mind if HTTP/2 clearly took the bull by the horns regarding I18N.

The easiest way to (re)encode UTF-8 using variable code length would be to collect/define statistics only for the leading octet and store the continuation octets as fixed 6-bit values (since they are restricted to the 80-BF range, 64 values).

-- 
Frédéric Kayser

[snip]

---

From: RUELLAN Herve <[email-masked]>
Date: Tue, 16 Apr 2013 15:56:50 +0000

I did some statistics on prefix sharing to find which header do most benefit from it.

==== Requests ====
:path                              :  96977
referer                            :  26060
cookie                             :  23081
:host                              :   5365
==== Responses ====
expires                            :  45442
last-modified                      :  44312
date                               :  42512
cache-control                      :  22096
via                                :  20106
content-length                     :   5603
set-cookie                         :   5337
server                             :   4019
age                                :   3845
content-type                       :   3675

For each header, the cumulated size of the shared prefixes is shown.

For responses, a large part of these headers can be optimized using a typed encoding. However, prefix sharing could still be useful for the remaining ones. For requests, none of the headers can be optimized with some typed encoding (except maybe the ":host" header).

Hervé.

> From: Adrien W. de Croy [mailto:[email-masked]]
> Sent: mardi 16 avril 2013 01:44
> To: James M Snell; RUELLAN Herve
> Cc: [email-masked]
> Subject: Re: Header Serialization Discussion
> 
> 
>

---

From: RUELLAN Herve <[email-masked]>
Date: Tue, 16 Apr 2013 16:06:51 +0000

> Sent: lundi 15 avril 2013 17:55
> To: RUELLAN Herve
> Cc: [email-masked]
> > I'd really like to keep the decoder as simple as possible, and so keeping all
> the buffer management on the encoder side is a real win for me.
> > In addition, the asymmetry means that the encoder is free to do whatever
> buffer management it wants. LRU is a very good default buffer management
> scheme, however I think there are cases where some clever scheme could
> beat it.
> 
> assigned in order and rotate, with used slots deallocated and reassigned as
> the buffer fills past it's limit. The encoder, then, needs to be selective about
> just what it decides to assign to the buffer. So long as an implementation
> follows the proper assignment order, the specific implementation does not
> matter.
> 

I'm afraid that using a "least recently written" queue would have a bad impact on compaction performances. There are some headers that don't change over a whole session (e.g. the user agent), or only take a few values over the whole session (e.g. accept). With a rotating scheme, these headers would have to be periodically re-added to the buffer.

Hervé.

---

From: James M Snell <[email-masked]>
Date: Tue, 16 Apr 2013 10:51:10 -0700

The compression ratio for requests will be a bit lower, yes, but I'm
purposefully trading off simplified, more predictable and more
controlled state management and higher throughput. I'm looking now to
see how best to support the shared prefix stuff using the typed codecs
to get more compression out of it. The compression ratio for responses
tends to be significantly better than delta2 and headerdiff in
testing, largely due to the use of the typed codecs.

Here are the test numbers I'm currently getting running against the
amazon.har  (dhe = "delta header encoding".. which is the new impl
based on what I described).

Requests:
               size  time | ratio min   max   std
     http1  200,876  0.01 | 1.00  1.00  1.00  0.00
       dhe   71,352  0.08 | 0.36  0.00  0.71  0.15
    delta2   35,850  0.37 | 0.18  0.03  0.67  0.12
headerdiff   38,673  0.23 | 0.19  0.03  0.88  0.16

Responses:
               size  time | ratio min   max   std
     http1  160,435  0.06 | 1.00  1.00  1.00  0.00
       dhe   37,132  0.02 | 0.23  0.00  0.66  0.11
    delta2   42,764  0.43 | 0.27  0.02  0.65  0.10
headerdiff   46,321  0.69 | 0.29  0.04  0.84  0.13

- James

---

From: James M Snell <[email-masked]>
Date: Tue, 16 Apr 2013 11:37:46 -0700

> headerdiff   46,321  0.69 | 0.29  0.04  0.84  0.13

I will note that these numbers reflect the fact that some header
fields are intentionally set as ephemeral so that they are never
stored in state. If I run the test again without that flag set for any
of the fields the numbers come out as...

REQUEST:
               size  time | ratio min   max   std
     http1  200,876  0.00 | 1.00  1.00  1.00  0.00
       dhe   40,957  0.06 | 0.20  0.00  0.71  0.14
    delta2   35,850  0.34 | 0.18  0.03  0.67  0.12
headerdiff   38,673  0.29 | 0.19  0.03  0.88  0.16

RESPONSE:
               size  time | ratio min   max   std
     http1  160,435  0.02 | 1.00  1.00  1.00  0.00
       dhe   35,350  0.02 | 0.22  0.00  0.67  0.12
    delta2   42,764  0.66 | 0.27  0.02  0.65  0.10
headerdiff   46,321  0.57 | 0.29  0.04  0.84  0.13

I still have more testing to do, of course, but that's where things stand now.

- James

---

From: Roberto Peon <[email-masked]>
Date: Tue, 16 Apr 2013 11:54:48 -0700

I also prefer just plain straight LRU. We can have some behavior which
allows for an item to be moved to the front of the LRU before it dies if
we're worried about it expiring and it is of high benefit.
(a flag on it saying it is 'permanent' or something as an option).

-=R

---

From: James M Snell <[email-masked]>
Date: Tue, 16 Apr 2013 14:00:15 -0700

Ok... I have a working implementation of the revised compression and
typed codecs I proposed. It is checked into github here [1]

[1] https://github.com/jasnell/http2/tree/master/src/snell/http2/headers/dhe

After pulling, you can test it with the compression_test suite using
the included dhe_compression_test.sh script

./compare_compressors.py -c
fork="{path_to_repo}/dhe_compression_test.sh"
../http_samples/mnot/amazon.com.har

Here are some sample numbers using the amazon set...

* TOTAL: 366 req messages
               size  time | ratio min   max   std
     http1  200,876  0.00 | 1.00  1.00  1.00  0.00
       dhe   51,427  0.02 | 0.26  0.00  0.71  0.16
    delta2   35,850  0.40 | 0.18  0.03  0.67  0.12
headerdiff   38,673  0.23 | 0.19  0.03  0.88  0.16

* TOTAL: 366 res messages
               size  time | ratio min   max   std
     http1  160,435  0.03 | 1.00  1.00  1.00  0.00
       dhe   51,487  0.05 | 0.32  0.01  0.80  0.16
    delta2   42,764  0.42 | 0.27  0.02  0.65  0.10
headerdiff   46,321  0.62 | 0.29  0.04  0.84  0.13

Using the yahoo test set, the numbers are...

* TOTAL: 142 req messages
               size  time | ratio min   max   std
     http1  107,164  0.00 | 1.00  1.00  1.00  0.00
       dhe   45,208  0.01 | 0.42  0.00  1.14  0.25
    delta2   46,529  0.27 | 0.43  0.05  0.79  0.22
headerdiff   52,739  0.05 | 0.49  0.04  0.94  0.26

* TOTAL: 142 res messages
               size  time | ratio min   max   std
     http1   59,718  0.00 | 1.00  1.00  1.00  0.00
       dhe   14,180  0.05 | 0.24  0.00  0.69  0.17
    delta2   16,148  0.17 | 0.27  0.02  0.69  0.17
headerdiff   18,599  0.02 | 0.31  0.04  0.85  0.23

- James

---

From: "Martin Nilsson" <[email-masked]>
Date: Wed, 17 Apr 2013 03:07:13 +0200

> variable length integer specifying the number of bytes.

I'll share what Opera Mini does for it's request protocol. It's a delta  
encoded name-value list statically assigned property identifiers and with  
a very minimal typing and length encoding. Since we control both client  
and server there are a lot of property specific value encodings used, but  
it doesn't change for a specific property (i.e. user strings are always  
UTF-8).

 From our documentation:

     Each property is encoded as eight flag bits followed by the id# of
     the property (16 bits) followed by the payload, the format of which
     depends on the flags.

      6bit         1bit    1bit     16 bit
     +---------+------+------+---------------+----------------- - -
     | unused  | INT  | LONG |  PROPERTY ID# | PAYLOAD
     +---------+------+------+---------------+----------------- - -

      if INT is 1, the payload is an integer, otherwise it's a string
      if LONG is 1, the payload length, or the integer, depending on INT,
      is 4 bytes long instead of 1 byte.

     -----+------+-----------------------------------------------------
      INT | LONG |  PAYLOAD
     -----+------+-----------------------------------------------------
       0  |  0   |  1 byte LEN (max 254), followed by LEN bytes data
       1  |  0   |  1 byte INT (value between 0 and 254)
       0  |  1   |  4 bytes LEN (max 0xfffffffe) followed by LEN bytes
       1  |  1   |  4 bytes INT (value between 0 and 0xffffffff)
     -----+------+------------------------------------------------------

     Only properties that have changed value need to be transmitted to
     the server, with a few exceptions.

Comparing with your proposal I would not create a specific Date Time type,  
but just keep it as an integer representation of posix time. I would not  
have different text encodings, but stick to only UTF-8. I would have a  
really serious thinking about if I should have both Binary and Text.

/Martin Nilsson

-- 
Using Opera's revolutionary email client: http://www.opera.com/mail/

---

From: James M Snell <[email-masked]>
Date: Tue, 16 Apr 2013 19:01:30 -0700

Another update... I just checked in preliminary support for UTF-8
support in the static huffman code. The basics are...

Building off of Roberto's dictionary, I added additional symbols to
the static huffman code tree, each representing a possible UTF-8
encoded length. Right now I have symbols for 2, 3, 4, 5 and 6 byte
lengths (yes, I know we don't need all those). For instance, in the
response table I have:

      (257) |110101 [6]
      (258) |110110 [6]
      (259) |01111 [5]
      (260) |10000 [5]
      (261) |10001 [5]

Where 257 is for 2 byte characters, 258 is for 3 byte, etc (I'm going
to be tweaking the tables so that this is better later).

As I iterate through each codepoint in the source text, I check to see
if the codepoint is < 256, if it is, I encode it normally. If the
codepoint > 256, I determine the appropriate escape code from the
table, then write the exact number of bits for the codepoint. So, for
instance, the supplementary character U+10400 is encoded out as [78 41
00 00], consuming a total of 26 bits.

This is purely experimental at this point, but the code is functional
and checked in to github. There are obviously a number of improvements
that could be made and I'm definitely open to more suggestions! One
problem with this, of course, is that it's not very efficient if the
field value consists primarily of extended characters -- that is, this
approach is optimized specifically for the case where we have the
random odd UTF-8 character thrown in to a mostly ASCII string.

One important side effect of this is that we ought to be able to "Just
Use UTF-8" across the board now, without requiring the ISO-8859-1
escape hatch.

- James

---

From: Frédéric Kayser <[email-masked]>
Date: Wed, 17 Apr 2013 16:02:37 +0200 (CEST)

Hello,
how could 110101 be used as prefix code for 257 since it's the beginning of prefix code 1101010 (61), the same goes for 110110 (258) beginning of 1101100 (83)...

Frédéric
----- Mail d'origine -----
De: James M Snell <[email-masked]>
À: [email-masked]
Envoyé: Wed, 17 Apr 2013 04:01:30 +0200 (CEST)
Objet: Re: Header Serialization Discussion

 (257) |110101 [6]
 (258) |110110 [6]
 (259) |01111 [5]
 (260) |10000 [5]
 (261) |10001 [5]

- James

---

From: Frédéric Kayser <[email-masked]>
Date: Wed, 17 Apr 2013 17:14:16 +0200 (CEST)

Ok based on Huffman.java you have apparently changed the other prefix codes accordingly and your sample was in fact for the request table.

Since UTF-8 is a superset of ISO Latin-1 and based on storeUtf8Codepoint it would cost at most 6+11 that's 17 bits to send an ISO Latin-1 code point encoded in UTF-8 compared to at least 25 bits in native form. I see two problems here:
17 bits is longer than 16 bits the raw UTF-8 size of such a code point
Why keep the long Latin-1 codes when their UTF-8 counter parts are shorter ?

I would suggest to build a new table keeping the statistics gathered for ASCII chars but using the upper part of the table to build prefix codes for UTF-8 leading octet C2—F4 range.
When encoding/decoding an UTF-8 codepoint if the leading octet was in the C2—DF range write/read 6 bits (a single continuation octet), if it was in the E0—EF range 12 bits (two continuation octets), and in the F0—F4 range 18 bits (three continuation octets).

Frédéric 

----- Mail d'origine -----
De: Frédéric Kayser <[email-masked]>
À: [email-masked]
Envoyé: Wed, 17 Apr 2013 16:02:37 +0200 (CEST)
Objet: Re: Header Serialization Discussion

Hello,

Frédéric
----- Mail d'origine -----
De: James M Snell <[email-masked]>
À: [email-masked]
Envoyé: Wed, 17 Apr 2013 04:01:30 +0200 (CEST)
Objet: Re: Header Serialization Discussion

 (257) |110101 [6]
 (258) |110110 [6]
 (259) |01111 [5]
 (260) |10000 [5]
 (261) |10001 [5]

- James

---

From: James M Snell <[email-masked]>
Date: Wed, 17 Apr 2013 10:31:18 -0700

Yeah, I was looking at that also. My concern was mainly how adding
symbols for each leading octet would affect the efficiency of the
ascii portion of the code tree but looking it over, the existing code
tree contains symbols for codepoints >= 127 already. If we drop those
generally unused higher codepoints, change the EOF from 256 to 127 and
add in the 50 leading octet symbols the resulting tree is very
reasonable. I've been playing with the frequency numbers and was able
to generate a tree where the leading octets can be encoded in exactly
8-bits. Then, as you suggest, write out 6-bits from each trailing
octet. This should give us a fairly compact encoding for all
codepoints >= 128.

---

From: Frédéric Kayser <[email-masked]>
Date: Wed, 17 Apr 2013 20:20:42 +0200 (CEST)

I think this is the way to go. The codepoints between 80 and FF where in the tree to encode ISO Latin-1 more precisely what is called Latin-1 Supplement in Unicode, it's the second Unicode block, leading octets C2 and C3 are used to access it in UTF-8. Allowing ISO Latin-1 in the header probably had sens in the 90s, nowadays Unicode and UTF-8 make a lot more sens.
But the question remains could we use UTF-8 text fields to store IRIs (RFC3987) in native form without punycode and percent escaping? More and more countries allow IDNs (Internationalized Domain Name) even ccTLDs can be internationalized nowadays. DNS protocols were stuck to ASCII but HTTP/2 has the opportunity to embrace Unicode.

Frédéric

---

From: James M Snell <[email-masked]>
Date: Wed, 17 Apr 2013 11:46:06 -0700

> I think this is the way to go. The codepoints between 80 and FF where in the tree to encode ISO Latin-1 more precisely what is called Latin-1 Supplement in Unicode, it's the second Unicode block, l…

Yep.. I have this working now and it does encode much more compactly.
I've ensured that the leading octet is encoded as an 8-bit prefix,
allowing us to encode the UTF-8 characters compactly with 2-fewer bits
per continuation byte.

> But the question remains could we use UTF-8 text fields to store IRIs (RFC3987) in native form without punycode and percent escaping? More and more countries allow IDNs (Internationalized Domain Na…

This is a more difficult question. In theory, yes, we ought to be able
to support these, but there's the question of backwards compatibility.
We could define that the new :path field (and referer, location, link,
etc) contain a UTF-8 encoded IRIs, so for backwards compatibility with
HTTP/1, an implementation would need to do the appropriate standard
conversion to a URI. Going the other direction, an impl could choose
to leave it as a URI or convert it to it's IRI form. I think this
makes a lot of sense and has a very clear http/2 <--> http/1
translation. So I'm +1 on it.

- James

---

From: James M Snell <[email-masked]>
Date: Wed, 17 Apr 2013 13:08:31 -0700

I've updated the implementation to use the revised scheme.

---

From: Martin Thomson <[email-masked]>
Date: Wed, 17 Apr 2013 14:40:10 -0700

Yeah, my first thought was to just use those to encode the raw UTF-8
octets, albeit at a great efficiency loss.  (non-ASCII-space
characters assumed to be not valid or rare).

The cost of dropping the other characters is that you now have another
table, assuming of course that you still care to huffman encode 8859-1
as well.

---

From: James Cloos <[email-masked]>
Date: Thu, 18 Apr 2013 14:11:10 -0400

>>>>> "JMS" == James M Snell <[email-masked]> writes:

JMS> This is a more difficult question. In theory, yes, we ought to be
JMS> able to support these, but there's the question of backwards
JMS> compatibility.  We could define that the new :path field (and
JMS> referer, location, link, etc) contain a UTF-8 encoded IRIs, so for
JMS> backwards compatibility with HTTP/1, an implementation would need
JMS> to do the appropriate standard conversion to a URI. Going the other
JMS> direction, an impl could choose to leave it as a URI or convert it
JMS> to it's IRI form. I think this makes a lot of sense and has a very
JMS> clear http/2 <--> http/1 translation. So I'm +1 on it.

I also like this, bug have to ask:  Do any non-10646 IRIs encode
differently depending on language?  Ie, would forcing everything
to 10646/utf8 loose information due to character unification?

Think of the differences between the zht, zhs, jp and ko glyphs
of characters unified by 10646.

Perhaps it doesn't matter, even if so?  Or perhaps the utf8 IRI should
be accompanied by a optional language hint?

-JimC
-- 
James Cloos <[email-masked]>         OpenPGP: 1024D/ED7DAEA6