Re: Straw Poll: Restore Header Table and Static Table Indices

[Willy Tarreau <[e-mail]>]

Hi Mark,

On Fri, Oct 17, 2014 at 10:23:35AM +1100, Mark Nottingham wrote:
> I think we need to see a proposal here if we?re going to take this seriously
> ? i.e., either fairly complete text or a pull request.

Here's the change I'm proposing. It's a diff against the text version because
it was easier for me to produce this, and it's easily readable by everyone here.

The diff looks like what's below, I think it addresses what was discussed in
a way that is pretty straightforward since there's no more the need to explain
the split between the two tables.

I have not changed anything else eventhough I'm seeing room for improvement
(eg: swapping encoding prefix of "literal without indexing" with the one
for "dynamic table size update" and gain one bit of encoding per header).

Anyone would please review and/or comment ?

Thanks,
Willy

------------

diff --git a/compression.txt b/compression.txt
index a4c8a40..56b2ea0 100644
--- a/compression.txt
+++ b/compression.txt
@@ -309,9 +309,6 @@ Internet-Draft                    HPACK                     October 2014
    (see Section 2.3.2) is dynamic and can be used by the encoder to
    index header fields repeated in the encoded header lists.
 
-   These two tables are combined into a single address space for
-   defining index values (see Section 2.3.3).
-
 2.3.1.  Static Table
 
    The static table consists of a predefined static list of header
@@ -348,37 +345,21 @@ Internet-Draft                    HPACK                     October 2014
 
 2.3.3.  Index Address Space
 
-   The static table and the dynamic table are combined into a single
-   index address space.
-
-   Indices between 1 and the length of the static table (inclusive)
-   refer to elements in the static table (see Section 2.3.1).
-
+   Both the static and the dynamic tables are indexed starting at 1.
    Indices strictly greater than the length of the static table refer to
    elements in the dynamic table (see Section 2.3.2).  The length of the
    static table is subtracted to find the index into the dynamic table.
 
-   Indices strictly greater than the sum of the lengths of both tables
-   MUST be treated as a decoding error.
+   Static table indices strictly greater than the length of the table as
+   defined in Appendix A MUST be treated as a decoding error. Dynamic table
+   indices strictly greater than the length of the dynamic table MUST be
+   treated as a decoding error.
 
-   For a static table size of s and a dynamic table size of k, the
-   following diagram shows the entire valid index address space.
-
-           <----------  Index Address Space ---------->
-           <-- Static  Table -->  <-- Dynamic Table -->
-           +---+-----------+---+  +---+-----------+---+
-           | 1 |    ...    | s |  |s+1|    ...    |s+k|
-           +---+-----------+---+  +---+-----------+---+
-                                  ^                   |
-                                  |                   V
-                           Insertion Point      Dropping Point
-
-                       Figure 1: Index Address Space
 
 2.4.  Header Field Representation
 
    An encoded header field can be represented either as a literal or as
-   an index.
+   an index in one of the tables.
 
    A literal representation defines a header field by specifying its
    name and value.  The header field name can be represented literally
@@ -740,14 +721,15 @@ Internet-Draft                    HPACK                     October 2014
 
      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
-   | 1 |        Index (7+)         |
-   +---+---------------------------+
+   | 1 | D |     Index (6+)        |
+   +---+---+---+---+---+---+---+---+
 
                       Figure 5: Indexed Header Field
 
-   An indexed header field starts with the '1' 1-bit pattern, followed
-   by the index of the matching pair, represented as an integer with a
-   7-bit prefix (see Section 5.1).
+   An indexed header field starts with the '1' 1-bit pattern, followed by
+   the D bit indicating if the index references the static table (0) or
+   the dynamic table (1), and the index of the matching pair, represented
+   as an integer with a 6-bit prefix (see Section 5.1).
 
    The index value of 0 is not used.  It MUST be treated as a decoding
    error if found in an indexed header field representation.
@@ -788,8 +770,8 @@ Internet-Draft                    HPACK                     October 2014
 
      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
-   | 0 | 1 |      Index (6+)       |
-   +---+---+-----------------------+
+   | 0 | 1 | D |  Index (5+)       |
+   +---+---+---+-------------------+
    | H |     Value Length (7+)     |
    +---+---------------------------+
    | Value String (Length octets)  |
@@ -800,8 +782,8 @@ Internet-Draft                    HPACK                     October 2014
 
      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
-   | 0 | 1 |           0           |
-   +---+---+-----------------------+
+   | 0 | 1 | 0 |       0           |
+   +---+---+---+-------------------+
    | H |     Name Length (7+)      |
    +---+---------------------------+
    |  Name String (Length octets)  |
@@ -819,11 +801,13 @@ Internet-Draft                    HPACK                     October 2014
    If the header field name matches the header field name of an entry
    stored in the static table or the dynamic table, the header field
    name can be represented using the index of that entry.  In this case,
-   the index of the entry is represented as an integer with a 6-bit
-   prefix (see Section 5.1).  This value is always non-zero.
+   the index of the entry is represented as the D bit indicating if the
+   index references the static table (0) or the dynamic table (1),
+   followed by an integer with a 5-bit prefix (see Section 5.1).  This
+   value is always non-zero.
 
    Otherwise, the header field name is represented as a literal string
-   (see Section 5.2).  A value 0 is used in place of the 6-bit index,
+   (see Section 5.2).  A value 0 is used in place of the 5-bit index,
    followed by the header field name.
 
    Either form of header field name representation is followed by the
@@ -844,8 +828,8 @@ Internet-Draft                    HPACK                     October 2014
 
      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
-   | 0 | 0 | 0 | 0 |  Index (4+)   |
-   +---+---+-----------------------+
+   | 0 | 0 | 0 | 0 | D | Index (3+)|
+   +---+---+---+---+---+-----------+
    | H |     Value Length (7+)     |
    +---+---------------------------+
    | Value String (Length octets)  |
@@ -855,8 +839,8 @@ Internet-Draft                    HPACK                     October 2014
 
      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
-   | 0 | 0 | 0 | 0 |       0       |
-   +---+---+-----------------------+
+   | 0 | 0 | 0 | 0 | 0 |     0     |
+   +---+---+---+---+---+-----------+
    | H |     Name Length (7+)      |
    +---+---------------------------+
    |  Name String (Length octets)  |
@@ -874,11 +858,13 @@ Internet-Draft                    HPACK                     October 2014
    If the header field name matches the header field name of an entry
    stored in the static table or the dynamic table, the header field
    name can be represented using the index of that entry.  In this case,
-   the index of the entry is represented as an integer with a 4-bit
-   prefix (see Section 5.1).  This value is always non-zero.
+   the index of the entry is represented as the D bit indicating if the
+   index references the static table (0) or the dynamic table (1),
+   followed by as an integer with a 3-bit prefix (see Section 5.1).
+   This value is always non-zero.
 
    Otherwise, the header field name is represented as a literal string
-   (see Section 5.2).  A value 0 is used in place of the 4-bit index,
+   (see Section 5.2).  A value 0 is used in place of the 3-bit index,
    followed by the header field name.
 
    Either form of header field name representation is followed by the
@@ -900,8 +886,8 @@ Internet-Draft                    HPACK                     October 2014
 
      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
-   | 0 | 0 | 0 | 1 |  Index (4+)   |
-   +---+---+-----------------------+
+   | 0 | 0 | 0 | 1 | D | Index (3+)|
+   +---+---+---+---+---+-----------+
    | H |     Value Length (7+)     |
    +---+---------------------------+
    | Value String (Length octets)  |
@@ -911,8 +897,8 @@ Internet-Draft                    HPACK                     October 2014
 
      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
-   | 0 | 0 | 0 | 1 |       0       |
-   +---+---+-----------------------+
+   | 0 | 0 | 0 | 1 | 0 |     0     |
+   +---+---+---+---+---+-----------+
    | H |     Name Length (7+)      |
    +---+---------------------------+
    |  Name String (Length octets)  |
@@ -957,7 +943,7 @@ Internet-Draft                    HPACK                     October 2014
      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
    | 0 | 0 | 1 |   Max size (5+)   |
-   +---+---------------------------+
+   +---+---+---+-------------------+
 
                Figure 12: Maximum Dynamic Table Size Change
 
------------