Subject: Delta Compression and UTF-8 Header Values

From: James M Snell <[email-masked]>
Date: Fri, 8 Feb 2013 11:28:04 -0800

Just going through more implementation details of the proposed delta
encoding... one of the items that had come up previously in early
http/2 discussions was the possibility of allowing for UTF-8 header
values. Doing so would allow us to move away from things like
punycode, pct-encoding, Q and B-Codecs, RFC 5987 mechanisms, etc it
would bring along a range of other issues we would need to deal with.

One key challenge with allowing UTF-8 values, however, is that it
conflicts with the use of the static huffman encoding in the proposed
Delta Encoding for header compression. If we allow for non-ascii
characters, the static huffman coding simply becomes too inefficient
and unmanageable to be useful. There are a few ways around it but none
of the strategies are all that attractive.

So the question is: do we want to allow UTF-8 header values? Is it
worth the trade-off in less-efficient header compression? Or put
another way, is increased compression efficiency worth ruling out
UTF-8 header values?

(Obviously there are other issues with UTF-8 values we'd need to
consider, such as http/1 interop)

- James

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Fri, 08 Feb 2013 19:35:16 +0000

Content-Type: text/plain; charset=ISO-8859-1
--------
In message <CABP7RbfRLXPpL4=wip=[email-masked]>
, James M Snell writes:

>So the question is: do we want to allow UTF-8 header values? 

Jim Gettys famously laid down some principles for X11 development,
number 1 and 3 of which are:

	1.Do not add new functionality unless an implementor cannot
	  complete a real application without it.

	3.The only thing worse than generalizing from one example
	  is generalizing from no examples at all.

Do we have two examples of what it is that somebody cannot do (in a
reasonable way?) without UTF-8 header values ?

-- 
Poul-Henning Kamp       | UNIX since Zilog Zeus 3.20
[email-masked]         | TCP/IP since RFC 956
FreeBSD committer       | BSD since 4.3-tahoe    
Never attribute to malice what can adequately be explained by incompetence.

---

From: James M Snell <[email-masked]>
Date: Fri, 8 Feb 2013 11:44:44 -0800

> reasonable way?) without UTF-8 header values ?

AFAIC, the main motivation for allowing UTF-8 headers is to reduce
(and *eventually* eliminate) the need for
punycode/pct-encoding/B-codec/Q-codec/RFC5987.

This is not so much a question of enabling a use case that cannot be
"resonably" done without UTF-8 headers. Rather, it's a question of
simplifying things for developers by reducing existing complexity (by
moving that complexity into the protocol).

- James

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Fri, 08 Feb 2013 19:50:40 +0000

Content-Type: text/plain; charset=ISO-8859-1
--------
In message <CABP7Rbd7bck4czG9c84hLeAHMnbeqb1mYhS+-DKKtZYEyia=[email-masked]>

>punycode/pct-encoding/B-codec/Q-codec/RFC5987.

I guess the relevant question then is: Are these headers where it
is necessary for HTTP entities to understand the value (ie:
"Cache-Control", "Location" etc, ) or headers which are just
transported transparently from end to end ("X-FOObar", "Cookie"
etc.)

In the latter case, supporting UTF-8 is merely a matter of letting
another bit through per byte, in the former case it opens a major
bucket of worms IMO.

---

From: Roberto Peon <[email-masked]>
Date: Fri, 8 Feb 2013 11:52:59 -0800

++

-=R

---

From: James M Snell <[email-masked]>
Date: Fri, 8 Feb 2013 12:21:50 -0800

On Feb 8, 2013 11:50 AM, "Poul-Henning Kamp" <[email-masked]> wrote:
[snip]
> another bit through per byte, in the former case it opens a major

No argument there. However, this bucket of worms is no worse than several
of the others we've already been considering :)

The key headers where this becomes the most relevant are :host, :path,
Content-Disposition, Link, and possibly Cookie/Set-Cookie (that's a big
maybe).

If nothing else, it would be helpful to have a single encoding defined for
all non-ascii header field values that can be indicated by a bit flag. E.g.
if the flag is set, value is hex encoded binary. It doesn't alleviate all
the issues, of course, but  does simplify things for app developers.

---

From: Mark Nottingham <[email-masked]>
Date: Sat, 9 Feb 2013 10:53:10 +1100

My .02 - 

RFC2616 implies that the range of characters available in headers is ISO-8859-1 (while tilting the table heavily towards ASCII), and we've clarified that in bis to recommend ASCII, while telling implementations to handle anything else as opaque bytes.

However, on the wire in HTTP/1, some bits are sent as UTF-8 (in particular, the request-URI, from one or two browsers).

I think our choices are roughly:

1) everything is opaque bytes
2) default to ASCII, flag headers using non-ASCII bytes to preserve them
3) everything is ASCII, require implementations that receive non-ASCII HTTP/1.1 to translate to ASCII (e.g., convert IRIs to URIs)

#1 is safest, but you don't get the benefit of re-encoding. The plan the the first implementation draft is to not try to take advantage of encoding, so it's the way we're likely to go -- for now.

#2 starts to walk down the encoding path. There are many variants; we could default to blobs, default to UTF-8, etc. We could just flag "ASCII or blob" or we could define many, many possible encodings, as discussed.

#3 seems risky to me.

Cheers, 

--
Mark Nottingham   http://www.mnot.net/

---

From: James M Snell <[email-masked]>
Date: Fri, 8 Feb 2013 17:10:02 -0800

> #2 starts to walk down the encoding path. There are many variants; we could default to blobs, default to UTF-8, etc. We could just flag "ASCII or blob" or we could define many, many possible encodi…

I have the distinct feeling we're going to end up somewhere between #1
and #2.. which means bad things for the static huffman-coding. If we
end up with #2, we'll be able to huffman code anything that is flagged
as ASCII, and won't be able to touch the rest.

- James

---

From: "Adrien W. de Croy" <[email-masked]>
Date: Sat, 09 Feb 2013 02:02:27 +0000

Hi

------ Original Message ------
From: "James M Snell" <[email-masked]>
To: "Poul-Henning Kamp" <[email-masked]>
Cc: "[email-masked]" <[email-masked]>
Sent: 9/02/2013 9:21:50 a.m.
Subject: Re: Delta Compression and UTF-8 Header Values
>On Feb 8, 2013 11:50 AM, "Poul-Henning Kamp" <[email-masked]> 
<snip>

>If nothing else, it would be helpful to have a single encoding defined 
>for all non-ascii header field values that can be indicated by a bit 
>flag. E.g. if the flag is set, value is hex encoded binary. It doesn't 
>alleviate all the issues, of course, but  does simplify things for app 
>developers.
>
do you mean just binary?  hex-encoded binary is just bloat for no good 
reason if your format is binary capable why would you double the size by 
hex-encoding it?

Adrien

---

From: Bjoern Hoehrmann <[email-masked]>
Date: Sat, 09 Feb 2013 03:19:35 +0100

>1) everything is opaque bytes

I can imagine some exceptions, like the `Host` header might be encoded
as UTF-8 if it is made into a separate "HTTP/2"-specific field, rather 
than carried as "normal header", but other than that I am pessimistic
about trying anything else.
-- 
Björn Höhrmann · mailto:[email-masked] · http://bjoern.hoehrmann.de
Am Badedeich 7 · Telefon: +49(0)160/4415681 · http://www.bjoernsworld.de
25899 Dagebüll · PGP Pub. KeyID: 0xA4357E78 · http://www.websitedev.de/

---

From: "Martin J. Dürst" <[email-masked]>
Date: Sat, 09 Feb 2013 21:36:57 +0900

On 2013/02/09 8:53, Mark Nottingham wrote:
> My .02 -
>
> RFC2616 implies that the range of characters available in headers is ISO-8859-1

That's a leftover from the *very* early 1990s, when ISO-8859-1 was 
actually a step forward from the various 'national' ISO-646 7-bit 
encodings. It was not a bad idea at that time by TimBL to make the Web 
work throughout Western Europe. UTF-8 wasn't even invented then.
(see http://www.cl.cam.ac.uk/~mgk25/ucs/utf-8-history.txt)

The IETF understood the advantages of UTF-8 in the late 1990s, see 
http://tools.ietf.org/html/rfc2277#section-3.1

These days, UTF-8 isn't a step forward, it's just plain obvious. The 
browser folks at WHATWG would prefer not to have any Web pages in 
anything else than UTF-8 anymore. That will take quite some time yet, 
but the trend is very clear. See e.g. 
http://googleblog.blogspot.jp/2010/01/unicode-nearing-50-of-web.html and
http://w3techs.com/technologies/details/en-utf8/all/all. Websockets was 
designed with UTF-8 and binary built in from the start. For all kinds of 
other protocols, UTF-8 is a non-brainer, too.

It would be a good idea to try hard to make the new protocol forward 
looking (or actually just acknowledge the present, rather than stay 
frozen in the past) for the next 20 years or so in terms of character 
encoding, too, and not only in terms of CPU/network performance.

And James is right, it would allow to throw out all kinds of encoding 
cruft. That doesn't affect performance through the pipes, but it clearly 
makes things a lot easier at the ends.

Regards,   Martin.

> (while tilting the table heavily towards ASCII), and we've clarified that in bis to recommend ASCII, while telling implementations to handle anything else as opaque bytes.

> On 09/02/2013, at 6:28 AM, James M Snell<[email-masked]>  wrote:
>

---

From: "Martin J. Dürst" <[email-masked]>
Date: Sat, 09 Feb 2013 21:45:55 +0900

> reasonable way?) without UTF-8 header values ?

Do you have two examples of what it is that somebody cannot do (in a 
reasonable way?) in Baudot code (5-bit)?

So why would HTTP use ASCII (and ISO-8859-1) in the first place?

Regards,   Martin.

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Sat, 09 Feb 2013 12:50:02 +0000

Content-Type: text/plain; charset=ISO-8859-1
--------
In message <[email-masked]>, =?UTF-8?B?Ik1hcnRpbiBKLiBEw7xyc3

>reasonable way?) in Baudot code (5-bit)?

Be funny ?

No, scratch that, I actually do know where there is a 5-hole punched
tape filled with old dirty jokes in Danish...

---

From: Willy Tarreau <[email-masked]>
Date: Sat, 9 Feb 2013 14:33:41 +0100

> encoding, too, and not only in terms of CPU/network performance.

Well, don't confuse UTF-8 and Unicode. UTF-8 is just a space-efficient way
of transporting Unicode characters for western countries. The encoding can
become inefficient to transport for other charsets by inflating data by up
to 50% and may make compression less efficient. Also, processing it is
particularly inefficient as you have to parse each and every byte to find
a length, making string comparisons quite slow.

I'm not saying I'm totally against UTF-8 in HTTP/2 (eventhough I hate using
it), I'm saying that it's not *THE* solution to every problem. It's just *A*
solution to *A* problem : "how to extend character sets in existing documents
without having to re-encode them all". I don't think this specific problem is
related to the scope of the HTTP/2 work, so at first glance, I'd say that
UTF-8 doesn't seem to solve a known problem here.

Regards,
Willy

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Sat, 09 Feb 2013 14:04:30 +0000

Content-Type: text/plain; charset=ISO-8859-1
--------
In message <[email-masked]>, Willy Tarreau writes:

>I'm not saying I'm totally against UTF-8 in HTTP/2 [...]

What and where do you mean when you say "UTF-8" In HTTP/2 ?

I think we need to be more precise, to avoid misunderstandings.

In HTTP/1, there is a peculiar mix between protocol-mechanics, and
metadata:  If I add a custom bit of metadata, it must follow certain
rules, since otherwise it will break the protocol mechanics.

For instance, I cannot define a custom header called:

	 "FOO" CRNL CRNL ": " [8 zero bytes]

If we define HTTP/2 as a "binary" protocol in some sensible way,
this restriction could go away, and we'd just move something like:

	<HDR nlen=7,blen=8> "FOO" CRNL CRNL \0\0\0\0\0\0\0\0

down the wire, and not care about what it is, what it means or
what character set, if any, it is encoded in.

It is only the metadata that needs inspection along the way where
we need to decide about UTF-8, and it really isn't that much.

Host:
	Why would we care about the character set ?  We're
	just going to pass it to DNS anyway.

URI:
	At least the query strings, possibly all of it ?
	But do we really care ?  Provided we take the Host
	part out, as proposed, we treat this as a unit.

Cache-Control:
	And what good would UTF-8 do here in the first place ?

So where is it you want UTF-8, and what difference will it make ?

---

From: "Martin Nilsson" <[email-masked]>
Date: Sat, 09 Feb 2013 15:12:32 +0100

On Sat, 09 Feb 2013 14:33:41 +0100, Willy Tarreau <[email-masked]> wrote:

> Also, processing it is

You don't need to know the length in characters to compare strings. Just  
comparing byte on byte works fine. Null is encoded the same, and byte zero  
only appear as null in UTF-8, so strlen works fine. So far strings are  
hollerith encoded in HTTP/2, so it should be a moot point anyway.

/Martin Nilsson

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

---

From: "Martin Nilsson" <[email-masked]>
Date: Sat, 09 Feb 2013 15:12:24 +0100

On Sat, 09 Feb 2013 00:53:10 +0100, Mark Nottingham <[email-masked]> wrote:

> My .02 -
>
> RFC2616 implies that the range of characters available in headers is  
> ISO-8859-1 (while tilting the table heavily towards ASCII), and we've  
> clarified that in bis to recommend ASCII, while telling implementations  
> to handle anything else as opaque bytes.
>
> However, on the wire in HTTP/1, some bits are sent as UTF-8 (in  
> particular, the request-URI, from one or two browsers).
>

I don't see a reason to not UTF-8 encode all text fields. HTTP/1 forced a  
lot of heuristic code that tried to figure out how things where  
transformed on the way, and heuristics for decoders are bad. Though, as  
the world has moved to UTF-8, saying "opaque bytes" means UTF-8 in  
practice for everyone anyway. The problem are fields that ideally should  
be binary, say a hash for ETag. UTF-8 encoding would add 50% size there.

Creating a static huffman code for the ASCII part of Unicode shouldn't be  
a problem, as long as there is a prefix for non-ascii bytes.

/Martin Nilsson

---

From: Albert Lunde <[email-masked]>
Date: Sat, 09 Feb 2013 08:14:38 -0600

> So where is it you want UTF-8, and what difference will it make ?

One legacy question that might be lurking is round-trip encoding between 
UTF-8 and the "encoded word" header encoding.

---

From: Willy Tarreau <[email-masked]>
Date: Sat, 9 Feb 2013 15:58:34 +0100

On Sat, Feb 09, 2013 at 03:12:32PM +0100, Martin Nilsson wrote:
> comparing byte on byte works fine.

This is exactly what you want to avoid when comparing with lots of strings.
It's generally more efficient to first compare lengths, then byte per byte
only if lengths match. This is equally true when checking for some regex
patterns such as "/cache/dir/../..../" where "." denotes a character. And
last but not least, the Boyer-Moore search is much less efficient with
UTF-8 encoding than what it is with non-encoded data.

I'm really all for just transporting raw data as much as possible, that
only the two ends need to understand and agree upon when it comes to the
encoding. However, if some data come from commonly UTF-8 encoded sources,
then I'd rather keep them as-is than having to re-encode them.

Willy

---

From: Willy Tarreau <[email-masked]>
Date: Sat, 9 Feb 2013 16:05:13 +0100

> we need to decide about UTF-8, and it really isn't that much.

Prefixing values with their lengths generally is the most efficient
way to work (CPU-wise).

> 	part out, as proposed, we treat this as a unit.

I'd be cautious about mixing URI and query strings, I see too often
people rewrite some requests to move the question mark away and
replace it with a slash. Then they don't realize they're possibly
mixing two distinct encodings, still they do!

> 	And what good would UTF-8 do here in the first place ?

No need, we need to use tokens here and tokens can be an enum.

> So where is it you want UTF-8, and what difference will it make ?

Hey Poul-Henning, please do not put words in my mouth, I'm not
saying I want UTF-8, OK ? As I said, I don't like this encoding at
all. What I'm saying is that if we have to transport such encoded
data, I prefer that we pass it as-is in its original form than having
to decode/encode it. For example, if it becomes a norm that URI,
Location or Referer is UTF8-encoded, let's pass them untransformed.

But in general, I think that 20 years of web have shown that the
protocol does not need this at all to succeed.

Regards,
Willy

---

From: Nico Williams <[email-masked]>
Date: Sat, 9 Feb 2013 11:47:48 -0600

> hollerith encoded in HTTP/2, so it should be a moot point anyway.

<insert pedantic comment about Unicode normalization here>

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Sat, 09 Feb 2013 17:59:33 +0000

>Hey Poul-Henning, please do not put words in my mouth, [...]

That was certainly not my intention, Willy, I picked your email only
because it contained the "UTF-8 in HTTP/2" expression.

>protocol does not need this at all to succeed.

Indeed.

---

From: "Adrien W. de Croy" <[email-masked]>
Date: Sat, 09 Feb 2013 21:33:13 +0000

------ Original Message ------
From: "Willy Tarreau" <[email-masked]>
>only if lengths match.

only if you don't have to count bytes to get the length.  IF you need to 
do that, then byte-by-byte is more efficient.

I guess we're talking about length-prefixed data in this context though 
so it would be an available optimisation.

Adrien

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Sat, 09 Feb 2013 22:09:31 +0000

Content-Type: text/plain; charset=ISO-8859-1
--------
In message <emf3ec6632-2c7a-491d-9db4-ad235e66f19c@bombed>, "Adrien W. de Croy"

>so it would be an available optimisation.

The optimization is usually even greater than that[1].

The str{n}cmp() family is forced to do byte-by-byte comparisons,
because the terminating NUL may be the last accessible byte in
virtual memory, so use of any wider type might trigger an "unwarranted"
page fault or segmentation violation.

If you know the strings to be long, you can sometimes amortize the
cost of checking if you are safely inside a VM page, but it is rarely
a useful general optimization.

Memcmp() having been told up front how many bytes it can assume are
valid to access, can use wider types to reduce number of instructions
speeding things up.  The memory system usually has byte-steering
logic which means that the number of memory operations for data is
the same in either case.

Compare for instance:
	http://svnweb.freebsd.org/base/head/lib/libc/arm/string/strncmp.S?revision=194585&view=markup

to:
	http://svnweb.freebsd.org/base/head/lib/libc/arm/string/memcmp.S?revision=137464&view=markup

The "identical alignment" requirement is caused by the ARM architectures
strong alignment, but it is worth keeping in mind also in protocol design:
It may be very profitable in speed to align and pad all strings to 16 or
even 32 bits.

Poul-Henning

[1] I wrote an article related to this some time ago:
	http://queue.acm.org/detail.cfm?id=2010365

[2] One protocol I helped improve originally had a string representation
    which paid attention to this:

	{
	uint16_t	length;
	uint16_t	__pad;
	uint32_t	data[];
	}

    But we still shaved about 20% CPU time, by turning the '__pad' word
    into a simple hash of the string:  It eliminated almost all full
    string comparisons.

    As much as I like this trick, I'm not sure I see many places in
    HTTP/2 where it would make much of a difference.

---

From: "Martin J. Dürst" <[email-masked]>
Date: Sun, 10 Feb 2013 13:31:39 +0900

Hello James, others,

> of the strategies are all that attractive.

[If somebody has pointers to actual code, that would be appreciated. I 
can't work on it for the next two weeks, but after that, I should be 
able to use a day or two to see what's possible.]

For a static Huffman encoding, you have to decide what symbols you 
accept as input, give every symbol a probability (these have to add up 
to 1) and then you get the 'optimal' "comma-free" encoding using the 
algorithm devised by Huffman. Optimal is under the assumptions that the 
probabilities are correct (and independent) and that you have to use an 
integral number of bits per symbol. Arithmetic coding gets rid of the 
second restriction, to get rid of the first, one creates a more complex 
model. Comma-free just means you don't have to guess where the bits for 
one symbol end and those for the next symbol start.

I'm not sure how the proposals came up with the probabilities, but I 
guess that was based on some data. Even though HTTP headers aren't 
English, I'd assume that 'e' has significantly higher probability than 
'Q' :-).

To make sure this works for UTF-8, the easiest way is to take bytes as 
input symbols. Some byte values with the high bit set can't appear in 
UTF-8, so these can be excluded. I'm not sure what the current proposals 
do, but I guess they also exclude many of the byte values in the C0 
range (0x00-0x1F), or at least give them very low probabilities.

A somewhat more complicated, but more efficient model would take the 
state of the UTF-8 'engine' into account, and have separate Huffman 
encoders for the various states, i.e. first byte of a character, second 
byte of a two-byte character, second byte of a three-byte character, 
third byte of a three-byte character, second/third/fourth byte of a 
four-byte character. Most if not all of the later ones can use the same 
Huffman encoder, and most probably can just assume a flat probability 
distribution and encode six raw bits (i.e. just eliminate the leading 
0b10 in trailing UTF-8 bytes).

If we think that ASCII is way more probable than UTF-8, then the only 
thing that will happen to ASCII is that one of the longest bit 
sequences, the one for the least probable ASCII byte, will get one bit 
longer. Of course, if we think that UTF-8 data is more probable, then 
there will be more changes, but these changes would be duly deserved.

Regards,    Martin.

---

From: "Martin J. Dürst" <[email-masked]>
Date: Sun, 10 Feb 2013 13:48:37 +0900

Hello Poul-Henning,

On 2013/02/09 21:50, Poul-Henning Kamp wrote:
> In message<[email-masked]>, =?UTF-8?B?Ik1hcnRpbiBKLiBEw7xyc3
> Qi?= writes:

While we are on a sideline, I'd hope you could have a close look at the 
above line. I'm not sure what kind of mail user agent you're using, but 
it doesn't look like a very recent one. It either doesn't understand 
UTF-8, or doesn't know that when copying =????=-encoded header values 
into the body, they need to be encoded differently.

For a contrast, here is how the corresponding line in Willy's mail looks 
(to increase the probability that you can read the actual characters, 

 > On Sat, Feb 09, 2013 at 09:36:57PM +0900, "Martin J. Dürst" wrote:

Just to make sure you don't misunderstand me, this is not about me and 
my name, but about about basic understanding for people who can't get by 
with just ASCII.

Regards,   Martin.

---

From: "Martin J. Dürst" <[email-masked]>
Date: Sun, 10 Feb 2013 14:02:46 +0900

Hello Willy,

> Well, don't confuse UTF-8 and Unicode.

As the main author of http://www.w3.org/TR/charmod/, I sure won't.

> UTF-8 is just a space-efficient way
> of transporting Unicode characters for western countries.

And for transporting ASCII-based commands/headers/markup together with 
non-ASCII data. That's the main reason the IETF adopted it.

> The encoding can
> to 50%

Well, that's actually an urban myth. The 50% is for CJK 
(Chinese/Japanese/Korean). For the languages/scripts of India, South 
East Asia, and a few more places, it can be 200%. (For texts purely in 
an alphabet in the Supplemental planes such as Old Italic, Shavian, 
Osmanya,..., it can be 300%, but I guess we can ignore these.) But these 
numbers only apply to cases that don't contain any ASCII at all.

> and may make compression less efficient.

That depends very much on the method of compression that's used.

> a length, making string comparisons quite slow.

[See the follow-up mails in this thread.]

> UTF-8 doesn't seem to solve a known problem here.

The fact that I mentioned Websockets may have lead to a 
misunderstanding. I'm not proposing to use UTF-8 only in bodies, just in 
headers (I wouldn't object, though). My understanding was that James was 
talking about headers, and I was doing so, too.

Regards,   Martin.

---

From: Roberto Peon <[email-masked]>
Date: Sat, 9 Feb 2013 21:18:53 -0800

The code checked in for the delta encoder either already encodes binary
values, or can be set to do so easily. The c++ version did-- the "unused"
symbols ended up with 32-bit outputs.
-=R

On Sat, Feb 9, 2013 at 8:31 PM, "Martin J. Dürst" <[email-masked]>wrote:

> can't work on it for the next two weeks, but after that, I should be able
> to use a day or two to see what's possible.]
>
> For a static Huffman encoding, you have to decide what symbols you accept
> as input, give every symbol a probability (these have to add up to 1) and
> then you get the 'optimal' "comma-free" encoding using the algorithm
> devised by Huffman. Optimal is under the assumptions that the probabilities
> are correct (and independent) and that you have to use an integral number
> of bits per symbol. Arithmetic coding gets rid of the second restriction,
> to get rid of the first, one creates a more complex model. Comma-free just
> means you don't have to guess where the bits for one symbol end and those
> for the next symbol start.
>
> I'm not sure how the proposals came up with the probabilities, but I guess
> that was based on some data. Even though HTTP headers aren't English, I'd
> assume that 'e' has significantly higher probability than 'Q' :-).
>
> do, but I guess they also exclude many of the byte values in the C0 range
> (0x00-0x1F), or at least give them very low probabilities.
>
> A somewhat more complicated, but more efficient model would take the state
> of the UTF-8 'engine' into account, and have separate Huffman encoders for
> the various states, i.e. first byte of a character, second byte of a
> two-byte character, second byte of a three-byte character, third byte of a
> three-byte character, second/third/fourth byte of a four-byte character.
> Most if not all of the later ones can use the same Huffman encoder, and
> most probably can just assume a flat probability distribution and encode
> six raw bits (i.e. just eliminate the leading 0b10 in trailing UTF-8 bytes).
>
> thing that will happen to ASCII is that one of the longest bit sequences,
> the one for the least probable ASCII byte, will get one bit longer. Of
> course, if we think that UTF-8 data is more probable, then there will be
> more changes, but these changes would be duly deserved.
>
> Regards,    Martin.
>
>

---

From: Frédéric Kayser <[email-masked]>
Date: Sun, 10 Feb 2013 07:44:19 +0100

Comparing Unicode strings without prior normalisation can lead to surprising results: "Frédéric" and "Frédéric" will probably look the same in your email client, but try to paste them in the search field and you'll probably see that they don't match since the first one uses precomposed diacritics and the second one combining ones.

Le 9 févr. 2013 à 15:12, Martin Nilsson a écrit :

> You don't need to know the length in characters to compare strings. Just comparing byte on byte works fine. Null is encoded the same, and byte zero only appear as null in UTF-8, so strlen works fine. So far strings are hollerith encoded in HTTP/2, so it should be a moot point anyway.

---

From: James M Snell <[email-masked]>
Date: Sat, 9 Feb 2013 22:51:06 -0800

When I initially tested it locally with a range of extended characters it
blew up on me. I will put together another set of tests and track down the
problem.
On Feb 9, 2013 9:18 PM, "Roberto Peon" <[email-masked]> wrote:

>> guess that was based on some data. Even though HTTP headers aren't English,
>> I'd assume that 'e' has significantly higher probability than 'Q' :-).
>>
>> byte of a two-byte character, second byte of a three-byte character, third
>> byte of a three-byte character, second/third/fourth byte of a four-byte
>> character. Most if not all of the later ones can use the same Huffman
>> encoder, and most probably can just assume a flat probability distribution
>> and encode six raw bits (i.e. just eliminate the leading 0b10 in trailing
>> UTF-8 bytes).
>>

---

From: Frédéric Kayser <[email-masked]>
Date: Sun, 10 Feb 2013 07:56:24 +0100

Ok my mail client normalized the text before sending it...

Text snippet in ZIP archive this time.

---

From: Roberto Peon <[email-masked]>
Date: Sat, 9 Feb 2013 23:02:42 -0800

You'll want to check that the table is full for entries above 127, and that
the EOF terminal is 256 as opposed to 128. I've gone back and forth so many
times on that part... :)
-=R

On Sat, Feb 9, 2013 at 10:51 PM, James M Snell <[email-masked]> wrote:

>> On Sat, Feb 9, 2013 at 8:31 PM, "Martin J. Dürst" <[email-masked]
>> > wrote:
>>
>>> Hello James, others,
>>>
>>>
>>> accept as input, give every symbol a probability (these have to add up to
>>> 1) and then you get the 'optimal' "comma-free" encoding using the algorithm

---

From: Willy Tarreau <[email-masked]>
Date: Sun, 10 Feb 2013 08:26:42 +0100

Hello Martin,

On Sun, Feb 10, 2013 at 02:02:46PM +0900, "Martin J. Dürst" wrote:
> (Chinese/Japanese/Korean).

With the fast development of China, it is perfectly imaginable that
in 10 years, a significant portion of the web traffic is made with
Chineese URLs, so we must not ignore that.

> For the languages/scripts of India, South 

I don't see how this is possible since you have 6 bits of data per byte
plus a few bits on the first byte, and you need 3 bytes to transport 16
bits, which is 50% for me :-)

> That depends very much on the method of compression that's used.

I agree, but adding unused bits or entropy in general will make compression
algorithms less efficient.

> talking about headers, and I was doing so, too.

I was talking about header values too. As a developer of intermediaries,
I'm not interested in the body at all. I'm seeing people do ugly things
all the time, like regex-matching hosts with ".*\.example\.com" without
being aware how slow it is to do that on each and every Host header field.
Typically doing that with an UTF-8 aware library is even slower.

That's why I'm having some concerns.

Ideally, everything we transport should be in its original form. If hosts
come from DNS, they should appear encoded as they were returned by the DNS
server (even with the ugly IDN format). If paths are supposed to be UTF-8,
let them be sent in their raw original UTF-8 form without changing the
format. But then we don't want to mix Host and path, and we want to put as
a first rule that only the shortest forms are allowed. If most header fields
are pure ASCII (eg: encodings), declare them as such. If some header fields
are enums, use enums and not text. Etc...

Regards,
Willy

---

From: James M Snell <[email-masked]>
Date: Sat, 9 Feb 2013 23:37:29 -0800

Keep in mind that allowing headers to potentially contain utf-8 does not
change the definitions of existing headers. Those that are currently
defined with ASCII only values would likely remain ASCII only; we would
need to either update the definitions of those existing headers (breaking
backwards compatibility) or define new utf-8 compatible replacements.

All we need to decide at this point, really, is a) are utf-8 header values
important to us and b) does/will our basic header encoding allow for utf-8
if the answer to (a) is yes.
On Feb 9, 2013 11:26 PM, "Willy Tarreau" <[email-masked]> wrote:

> > >without having to re-encode them all". I don't think this specific
> problem
> > >is

---

From: Frédéric Kayser <[email-masked]>
Date: Sun, 10 Feb 2013 08:49:44 +0100

Well, actually you don't need the full [80...FF] range since there a few values are not allowed (RFC 3629) these are C0, C1 and  F5 to FF.
The [80...BF] range can also be excluded for the lead octet since those are reserved for continuation octets.

I hope this helps:

Le 10 févr. 2013 à 08:02, Roberto Peon a écrit :

> You'll want to check that the table is full for entries above 127, and that the EOF terminal is 256 as opposed to 128. I've gone back and forth so many times on that part... :)
> -=R

---

From: Roberto Peon <[email-masked]>
Date: Sun, 10 Feb 2013 00:00:34 -0800

That is true for utf-8, but I made no such assumptions about what might
possibly be encoded... :)
-=R

On Sat, Feb 9, 2013 at 11:49 PM, Frédéric Kayser <[email-masked]> wrote:

> Well, actually you don't need the full [80...FF] range since there a few
> values are not allowed (RFC 3629) these are C0, C1 and  F5 to FF.
> > You'll want to check that the table is full for entries above 127, and
> that the EOF terminal is 256 as opposed to 128. I've gone back and forth so
> many times on that part... :)
> > -=R
>
>
>

---

From: Nico Williams <[email-masked]>
Date: Sun, 10 Feb 2013 02:17:04 -0600

>> of the strategies are all that attractive.
Wait, what?  If you have non-English (worse, non-European) text in some
ASCII encoding like punycode, or base64-encoded UTF-8, then static Huffman
will not be useful for compression anyways (assuming Huffman coding is
based on English -say- letter frequencies).

> for the next symbol start.

Right.  i hope i put it more succintly above.

The fact is that Huffman coding for all our scripts at once just isn't
possible.  Static Huffman coding is not a good reason to not want UTF-8 or
any other Unicode encoding.

Nico
--

---

From: Roberto Peon <[email-masked]>
Date: Sun, 10 Feb 2013 01:00:19 -0800

I'll point out that the only reason that we're talking about static
huffmans is because it isn't safe to have a constantly mutating huffman
encoding over the lifetime of the session.
Perhaps it is reasonable to negotiate a different table in the first
exchange, dunno, but it is certainly techincailly feasible.

That being said, dealing with utf-8 and unicode in metadata that isn't
being shown to the user seems silly to me.
For data which is, however, then picking one single encoding for it would
be nice, even if it is utf-8 :)
-=R

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Sun, 10 Feb 2013 09:28:27 +0000

Content-Type: text/plain; charset=ISO-8859-1
--------
In message <[email-masked]>, =?ISO-8859-1?Q?=22Martin_J=2E_D=
FCrst=22?= writes:

>above line. I'm not sure what kind of mail user agent you're using,

I'm using a pretty antique "nmh", and some decade I'll upgrade to
something which might or might not work better.

>my name, but about about basic understanding for people who can't get by 

I'm Danish, I know full well that ASCII isn't enough for people.

But protocols are not people, and while the are used to move the
communications of people, and therefore should be able to _move_
unicode, there is seldom, if ever, need nor advantage to pollute
the mechanics of the protocol with unicode.

This is why I keep asking people where _exactly_ it is they want
the unicode to go in the HTTP/2 protocol.  So far I fail to detect
a clear answer...

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Sun, 10 Feb 2013 09:38:03 +0000

Content-Type: text/plain; charset=ISO-8859-1
--------
In message <[email-masked]>, =?iso-8859-1?Q?Fr=E9
d=E9ric_Kayser?= writes:

>Comparing Unicode strings without prior normalisation can lead to =
>surprising results: "Fr=E9d=E9ric" and "Fr=E9d=E9ric" [...]

Indeed they do :)  (Yes, I noticed your second email)

But where in the HTTP/2 protocol is it exactly that you want to introduce
diacritics ?

	Cäché-Cöntrøl: Not-in-Europe

anyone ?

> Chineese URLs, so we must not ignore that.

I would just ignore it.

The only two places which care about the character-set of the URL,
is the ultimate client and the ultimate server, to everybody else,
it is just a sequence of opaque bits, which they must treat as a
indivisible unit.

Please somebody give men an example of exactly where in a HTTP/2
protocol session a HTTP protocol entity, (as opposed to the
ultimate consumer or producer of the information), cannot simply
use memcmp(), but needs to know the characterset encoding ?

---

From: Julian Reschke <[email-masked]>
Date: Sun, 10 Feb 2013 10:44:46 +0100

Indeed.

But note than in practice, B-codec and Q-codec aren't used.

That still leaves us with the other schemes.

Best regards, Julian

---

From: Julian Reschke <[email-masked]>
Date: Sun, 10 Feb 2013 10:47:01 +0100

> the unicode to go in the HTTP/2 protocol.  So far I fail to detect

1) Filenames in Content-Disposition

2) non-ASCII characters in HTTP auth credentials

3) title parameters in Link header fields

Best regards, Julian

---

From: Julian Reschke <[email-masked]>
Date: Sun, 10 Feb 2013 10:48:55 +0100

> UTF-8 and the "encoded word" header encoding.

Do we have evidence of "encoded word" being used anywhere?

Best regards, Julian

---

From: Willy Tarreau <[email-masked]>
Date: Sun, 10 Feb 2013 11:12:48 +0100

> it is just a sequence of opaque bits, which they must treat as a

It's not that much opaque when your "HTTP router" has to be able to
match part of that URL to decide where to route the requests. It's
particularly painful when the admin has to use specific encodings
in config files to write correct configurations :-/

Willy

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Sun, 10 Feb 2013 10:24:15 +0000

>1) Filenames in Content-Disposition

These only have meaning to the ultimate destinations, and if their
filesystems don't support UTF-8, they'll have to do $something anyway.

Nobody in the HTTP/2 protocol-chain can do anything but treat this
as an opaque bytestring.

>2) non-ASCII characters in HTTP auth credentials

Same.

>3) title parameters in Link header fields

Same.

The UTF-8 Questions imply does not apply at the protocol layer,
it only applies to the semantic interpretation at the ends of
the HTTP/2 protocol connection.

Or to put it more precisely:  I can see no place where an
HTTP/2 intermediate without a semantic role will ever need
to know about normalizing UTF-8 strings.

Agree ?

Since we, presumably, split HTTP into a transport and semantic
part in HTTPbis, and since HTTP/2 is not supposed to change
the semantics, why are we even discussing "UTF-8 in HTTP/2" ?

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Sun, 10 Feb 2013 10:29:12 +0000

Content-Type: text/plain; charset=ISO-8859-1
--------
In message <[email-masked]>, Willy Tarreau writes:
>match part of that URL to decide where to route the requests. 

First of all, the only non-semantic criteria you can route HTTP
requests on are the Host: header.  (Which we just pass to DNS,
so we don't care if it is UTF-8 or not).

As soon as you look at the URL, you dive into semantics, and you
had better have an agreement with the content-provider about what
those semantics (including char-set) and routing-criteria should be.

---

From: Willy Tarreau <[email-masked]>
Date: Sun, 10 Feb 2013 12:05:14 +0100

> those semantics (including char-set) and routing-criteria should be.

The content provider is the same as the one which sets the routing rules.
The 2 typical uses are :
  - send static objects to a dedicated farm
  - bypass caches for definitely non-cacheable objects

I would love to see only configurations where Host is the only
criterion but real world differs from the ideal one.

Willy

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Sun, 10 Feb 2013 11:08:49 +0000

>The content provider is the same as the one which sets the routing rules.

And that's the point:  A URL is a transparant sequence of bytes, unless
you have a private agreement with the content provider.

>criterion but real world differs from the ideal one.

Lots of web-hosting companies can show that to you.

---

From: Mark Nottingham <[email-masked]>
Date: Sun, 10 Feb 2013 22:22:38 +1100

Not picking on anyone in particular here, but you guys seem to be going in circles (as this is message 49 in this thread, by my count).

Deciding to re-encode EXISTING protocol artefacts is a big decision that should not be taken lightly. 

As such, it's not much good use of your time to ponder on the minutia of different ways to do it until we actually make that decision.

Of course, if that's what floats your boats, by all means. It's just that we have a plan to get to a first implementation draft (which does NOT include this), and a lot to do to get there, and I don't see how hyper-focusing on this issue right now helps. 

Cheers,

---

From: Roberto Peon <[email-masked]>
Date: Sun, 10 Feb 2013 13:04:31 -0800

Another place where we may need to know about normalization is for caching.
Does the lookup, etc. occur on the normalized form, or on the given data?

All in all, utf-8 without addendum sucks for protocol work.
-=R

---

From: Zhong Yu <[email-masked]>
Date: Sun, 10 Feb 2013 16:49:01 -0600

> Nobody in the HTTP/2 protocol-chain can do anything but treat this

But how does the 2 ends agree on which encoding to use? It might be
easier if HTTP just dictate UTF-8.

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Sun, 10 Feb 2013 22:52:18 +0000

Content-Type: text/plain; charset=ISO-8859-1
--------
In message <CACuKZqHMQdktfOU3PJC=X-G8R=BQ40bhFJw=ZTfeSpem9L=[email-masked]>

>easier if HTTP just dictate UTF-8.

But this is a semantic question, I've been told in no uncertain
terms that all that was settled in HTTPbis, and that HTTP/2 is
only about transport, and that reopening semantic questions was
Not To Be Done.

Did I misunderstand that ?

---

From: Zhong Yu <[email-masked]>
Date: Sun, 10 Feb 2013 16:58:30 -0600

> Chineese URLs, so we must not ignore that.

The problem of Chinese character in URL is %-encoding:

    %##%##%##

9 bytes for a single Chinese character! where ideally 2 bytes should suffice.

However, this is a URI issue, not an HTTP issue. Is HTTP going to
unilaterally "upgrade" URI format? That is possible, but it seems a
big step, and it'll only decease interop for some coming years.

>From my perspective, URLs are not a priority to optimize; they are
usually not that big; servers can unilaterally use a more efficient
encoding method for special chars. Maybe we should restraint from
trying to change URI syntax.

Zhong Yu

---

From: Zhong Yu <[email-masked]>
Date: Sun, 10 Feb 2013 17:03:39 -0600

> only about transport, and that reopening semantic questions was

I think that HTTP is supposed to transport "characters" in headers,
not "octets". So if we enlarge the legal character set by a wider
encoding scheme, can we define that change as a transport issue?

---

From: Zhong Yu <[email-masked]>
Date: Sun, 10 Feb 2013 17:25:36 -0600

> big step, and it'll only decease interop for some coming years.

... and I did not know about IRI...

Is HTTP2 going to adopt IRI?

---

From: Nico Williams <[email-masked]>
Date: Sun, 10 Feb 2013 18:09:14 -0600

>> filesystems don't support UTF-8, they'll have to do $something anyway.

The filesystems pretty much do support either UTF-8 or "just-use-8".
In general "just-use-8" only really interops if everyone uses the same
codeset, and the only codeset we have that can be used universally
is... Unicode.

> easier if HTTP just dictate UTF-8.

Not might be.  Will be.

We've done this in many other protocols.  In general we must either
tag text with codeset metadata or declare that Unicode (UTF-8,
generally) SHALL be used in the middle (and pushing codeset
conversions to the edge.  No character set other than Unicode is
suitable for use "in the middle", and tagging strings with codeset
metadata is particularly difficult.

It might be useful to go over what we've done in filesystems and
remote/distributed filesystem protocols.  Very briefly, in ZFS we
implemented fast normalization-insensitive string comparison and
hashing functionality; the filesystem has an option to reject any
non-UTF-8 byte sequences, but otherwise never normalizes on CREATE
(compare to HFS+).  Meanwhile NFSv4 calls for using only UTF-8 on the
wire.  This works.  It works *really* well.  The code is even open
source.  Filesystems are a great example of an application where
tagging strings with codeset metadata doesn't work: we'd need to push
process setlocale information into the kernel, and tag strings all the
way from the system call boundary -through the VFS- to the filesystem
driver -- with consequent impact on stable interfaces up and down the
stack, and massive code modifications requirements.

Filesystems are not the only example of this, but because filesystems
cross so many layers in our stacks (user-land APIs, kernel-land APIs,
on-the-wire protocols, on-disk formats) they are perhaps the best
example.

UTF-8 in the middle.

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Sun, 10 Feb 2013 18:12:54 -0600

> Did I misunderstand that ?

I don't know.  I wasn't there.  But where HTTP/2.0 carries text in the
headers, that text must either be US-ASCII only, or UTF-8 only -- no
other codesets, encodings, nothing.  Anything else will result in
just-send-8/just-use-8 and associated interop failures OR de facto
agreement to just-send-UTF-8.  The latter would be fine, but better
make it de jure.  If this was decided incorrectly in the past then the
decision needs to be open to review: I guarantee this will come up in
IETF and IESG review.  Better get it right now.

Nico
--

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Mon, 11 Feb 2013 00:15:30 +0000

Content-Type: text/plain; charset=ISO-8859-1
--------
In message <[email-masked]>

>> easier if HTTP just dictate UTF-8.

Really ?

I have a hard time squaring that with the "HTTP/2 is just a transport
protocol, we don't change the semantics" credo that was waved around
rather forcefully previously ?

And if we are going to change semantics, shouldn't we change the
ones that really matter[1] ?

Poul-Henning

[1] We can probably do much more for transmission efficiency by killing
cookies and adding client provided session-identifieres, than any
kind of encoding or compression will ever be able to...[2]

[2] Not to mention the improved privacy and legal compliance that
would automatically buy everybody...

---

From: Nico Williams <[email-masked]>
Date: Sun, 10 Feb 2013 18:16:02 -0600

> IETF and IESG review.  Better get it right now.

I suppose I should qualify this by saying that header text slots where
other standards apply, such as hostnames (IDNA) and IRIs, the protocol
can leave the matter to those standards.  But that need not be trivial
either: for domainname slots we might need to say only A-labels apply.

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Sun, 10 Feb 2013 18:18:53 -0600

> rather forcefully previously ?

I'm talking about *header* data, not payloads.  HTTP/2.0 is just a
transport as far as the data goes, but there is metadata too.

> kind of encoding or compression will ever be able to...[2]

Sort of.  Servers will still want to store state on the client side
(generally encrypted, thus not further compressible).  See
http://tools.ietf.org/html/draft-williams-websec-session-continue-prob-00
.

> would automatically buy everybody...

Yes, see draft-williams-websec-session-continue-prob-00 (and -proto-00).

Nico
--

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sun, 10 Feb 2013 20:49:49 -0500

On Sun, Feb 10, 2013 at 7:15 PM, Poul-Henning Kamp <[email-masked]>wrote:

> In message <
> [email-masked]>
> , Nico Williams writes:
>

Changing from US-ASCII encoded URIs to UTF8 encoded IRIs would seem like a
syntax issue to me, not semantics at all.

Since we are looking at coding efficiency it seems to me that we should at
least be open to specifying the length of the URI by means of a length
prefix rather than a space or CRLF separator. So I can't see a reason not
to consider UTF8 encoding of the URL which is only a syntax change when all
is said and done. Giving it a different name does not make it semantic.

Since the world is moving to UTF8, it would seem that getting HTTP fully in
sync with UTF8 would be the main motive for applications to move to HTTP2.
Unless we are looking for a full employment and a HTTP3 to follow.

-- 
Website: http://hallambaker.com/

---

From: James Cloos <[email-masked]>
Date: Mon, 11 Feb 2013 16:34:03 -0500

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

JMS> we'll be able to huffman code anything that is flagged
JMS> as ASCII, and won't be able to touch the rest.

Would that really be an issue?  The static huffman can only really be
for the common strings, yes?  Which mostly means the header names and
not the header values?  So even if the headers were limited to ascii
the tables wouldn't help much for most of the values?

(As an aside, Would arithmetic be of any better value than huffman, here?)

Using one bit for each string to specify utf8-text blob vs binary blob,
and using the former for everthing know to be text, seems the best
overall choice.  And if any non-ascii utf8 sequences become common
enough, they can be added to future revisions of the static table just
as easily as 7-bit strings can be.

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

---

From: Roberto Peon <[email-masked]>
Date: Mon, 11 Feb 2013 14:53:01 -0800

The header names are almost completely handled with the pre-seeded
dictionary, so they really don't affect the character frequency count
and/or thus the huffman encoding.

Arithmetic coding gets better compression ratios, at the expense of gobs of
CPU and complexity. I don't think that is a good tradeoff :/
We're proposing thus far that we encode with the static huffman, and if the
end-result is larger than the original text, just use the original text. Of
course, one could skip the huffman-encoding step if one had a good idea
that this would be the case, but hopefully we get close enough that the
static huffman is still of benefit. The way of doing this selection is
exactly what you propose-- use up a bit to indicate that the encoding isn't
done with huffman. There are a couple obvious ways of doing this:
1) Use a flag in the opcode byte. The main advantage of doing this is that
it saves bits elsewhere, but there is a disadvantage: If you end up wanting
to encode strings in two different ways, you must emit two different
opcodes of the same type, and each opcode ends up consuming 2-bytes (one
for opcode+flags, one for number of operations of that type).

-=R

---

From: James Cloos <[email-masked]>
Date: Tue, 12 Feb 2013 18:41:09 -0500

>>>>> "RP" == Roberto Peon <[email-masked]> writes:

RP> The header names are almost completely handled with the pre-seeded
RP> dictionary, so they really don't affect the character frequency
RP> count and/or thus the huffman encoding.

RP> Arithmetic coding gets better compression ratios, at the expense of
RP> gobs of CPU and complexity. I don't think that is a good tradeoff :/

It is sometimes hard to guess whether huffman is chosen due to inertia,
arithmetic patent agnst, or good technical reasons.  It is good to know
that in this case it is the latter.

I may not have expressed my primary point quite well enough though:

Although I doubt that right now there is any text in the headers which
is both common enough to warrent inclusion in a static table and not
seven-bit clean, my point was that even if such text shows up over time,
the fact that it is not seven-bit should not prevent its inclusion in
future, extended versions of the static table.  As such specifying that
text is defined to be utf-8 and the use of a static huffman table should
not contra-indicate each other.

-JimC

---

From: Roberto Peon <[email-masked]>
Date: Tue, 12 Feb 2013 16:01:04 -0800

Agreed.
-=R