Subject: Re: [Technical Errata Reported] RFC7541 (4574)

From: Pavel Rappo <[email-masked]>
Date: Wed, 30 May 2018 17:31:16 +0100

Sorry as I'm awkwardly late for the discussion. May I add my 2 cents
anyways? If there's a mention of a sorted list, there must be a
mention of the corresponding sorting order. I guess in this case,
Christian meant lexicograpical order. At least, it would be consistent
with the proposed changes to the list. I believe the name of the
sorting order should be added to the final wording of errata.

The logical consequence of the paragraph above is that if people want
to use binary search on this list of header fields, they still can do
it. They still can treat this list as sorted. After all, it's just a
matter of choosing the right sorting order, isn't it?

Implementing this "almost-lexicoghraphical" order (for the case of
Latin-1 strings) requires a small amount of code. The example is in
the Java language, where the java.util.Comparator object is in charge
of defining a sorting order:

public int compare(String s1, String s2) {
    int n = Math.min(s1.length(), s2.length());
    for (int i = 0; i < n; i++) {
        char c1 = s1.charAt(i);
        char c2 = s2.charAt(i);
        if (c1 == c2) {
            continue;
        } else if (c1 < c2) {
            return -1;
        } else {
            return 0;
        }
    }
    // a crucial moment: inverting the lexicographical order in the
    // case of a common prefix
    return s2.length() - s1.length();
}

Thanks,
-Pavel

On Thu, Dec 31, 2015 at 12:15 AM, RFC Errata System
<[email-masked]> wrote:
> The following errata report has been submitted for RFC7541,
> "HPACK: Header Compression for HTTP/2".
>
> --------------------------------------
> You may review the report below and at:
> http://www.rfc-editor.org/errata_search.php?rfc=7541&eid=4574
>
> --------------------------------------
> Type: Technical
> Reported by: Christian Parpart <[email-masked]>
>
> Section: Appendix A.
>
> Original Text
> -------------
>    Table 1 lists the predefined header fields that make up the static
>    table and gives the index of each entry.
>
>
> Corrected Text
> --------------
>    Table 1 lists the predefined header fields that make up the static
>    table and gives the index of each entry.
>
>    This list of predefined header fields is NOT sorted.
>
>
> Notes
> -----
> The list of header fields actually is sorted except for one field. The field with index 19 should be between the fields with index 14 and 15).
>
> That is why it gives the false impression that an implementer may use binary search algorithm to look up for header fields (while encoding) in order to retrieve their index numbers.
>
> I highly encourage to at either move that field up or at least clarify that this list (even though it looks sorted), it is not.
>
> Instructions:
> -------------
> This erratum is currently posted as "Reported". If necessary, please
> use "Reply All" to discuss whether it should be verified or
> rejected. When a decision is reached, the verifying party (IESG)
> can log in to change the status and edit the report, if necessary.
>
> --------------------------------------
> RFC7541 (draft-ietf-httpbis-header-compression-12)
> --------------------------------------
> Title               : HPACK: Header Compression for HTTP/2
> Publication Date    : May 2015
> Author(s)           : R. Peon, H. Ruellan
> Category            : PROPOSED STANDARD
> Source              : Hypertext Transfer Protocol Bis APP
> Area                : Applications
> Stream              : IETF
> Verifying Party     : IESG
>
>